如何使用Python实现链表的归并排序（Merge Sort）
链表归并排序的实现思路如下：
1.将链表分成两个部分，通过快慢指针的方式，慢指针指向链表的头部，快指针每次移动两个节点，当快指针遍历到链表末尾时，慢指针就指向了链表的中间节点，然后将链表从中间节点断开。
2.递归地对两个链表进行归并排序，直到每个子链表只有一个节点时，然后再将已排序的子链表合并成一个有序链表。
具体的Python代码实现如下：
# 定义链表节点 class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next # 链表归并排序 def merge_sort(head): if not head or not head.next: return head # 快慢指针寻找链表中点 slow, fast = head, head.next while fast and fast.next: slow, fast = slow.next, fast.next.next # 断开链表，并递归排序 mid, slow.next = slow.next, None left, right = merge_sort(head), merge_sort(mid) # 合并已排序的子链表 sorted_list = ListNode() cur = sorted_list while left and right: if left.val < right.val: cur.next = left left = left.next else: cur.next = right right = right.next cur = cur.next cur.next = left if left is not None else right return sorted_list.next # 打印链表 def print_list(head): res = '' while head: res += str(head.val) + ' -> ' head = head.next print(res + 'None') # 测试代码 if __name__ == '__main__': head = ListNode(3, ListNode(1, ListNode(4, ListNode(2, ListNode(5))))) print('排序前：') print_list(head) sorted_head = merge_sort(head) print('排序后：') print_list(sorted_head)
输出结果如下：
排序前： 3 -> 1 -> 4 -> 2 -> 5 -> None 排序后： 1 -> 2 -> 3 -> 4 -> 5 -> None
相关文章