2.6 链表归并排序

ITCharge大约 2 分钟

2.6 链表归并排序

---

1. 链表归并排序算法描述

分割环节：找到链表中心链节点，从中心节点将链表断开，并递归进行分割。
1. 使用快慢指针 fast = head.next、slow = head，让 fast 每次移动 2 步，slow 移动 1 步，移动到链表末尾，从而找到链表中心链节点，即 slow。
2. 从中心位置将链表从中心位置分为左右两个链表 left_head 和 right_head，并从中心位置将其断开，即 slow.next = None。
3. 对左右两个链表分别进行递归分割，直到每个链表中只包含一个链节点。
归并环节：将递归后的链表进行两两归并，完成一遍后每个子链表长度加倍。重复进行归并操作，直到得到完整的链表。
1. 使用哑节点 dummy_head 构造一个头节点，并使用 cur 指向 dummy_head 用于遍历。
2. 比较两个链表头节点 left 和 right 的值大小。将较小的头节点加入到合并后的链表中，并向后移动该链表的头节点指针。
3. 然后重复上一步操作，直到两个链表中出现链表为空的情况。
4. 将剩余链表插入到合并后的链表中。
5. 将哑节点 dummy_dead 的下一个链节点 dummy_head.next 作为合并后的头节点返回。

2. 链表归并排序实现代码

class Solution:
    def merge(self, left, right):
        # 归并环节
        dummy_head = ListNode(-1)
        cur = dummy_head
        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
        
        if left:
            cur.next = left
        elif right:
            cur.next = right
            
        return dummy_head.next
        
    def mergeSort(self, head: ListNode):
        # 分割环节
        if not head or not head.next:
            return head
        
        # 快慢指针找到中心链节点
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next 
            fast = fast.next.next 
        
        # 断开左右链节点
        left_head, right_head = head, slow.next 
        slow.next = None
        
        # 归并操作
        return self.merge(self.mergeSort(left_head), self.mergeSort(right_head))

    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        return self.mergeSort(head)

3. 链表归并排序算法复杂度分析

时间复杂度： $O(n \times \log_2n)$ 。
空间复杂度： $O(1)$ 。

2.6 链表归并排序

2.6 链表归并排序

1. 链表归并排序算法描述

2. 链表归并排序实现代码

3. 链表归并排序算法复杂度分析

练习题目