Skip to main content

148. Sort List

解题思路​

题目要求对链表进行排序，要求 O(n log n) 的时间复杂度，意味着我们不能使用冒泡排序、插入排序等 O(n²) 复杂度的算法，而应该使用 归并排序 或 快速排序。

由于链表不支持随机访问，我们更适合使用 归并排序：

  1. 找到链表的中点：使用快慢指针（Fast & Slow Pointer）。
  2. 递归地拆分链表：将链表拆成两部分并分别排序。
  3. 合并两个有序链表：使用归并操作（Merge Two Sorted Lists）。

归并排序实现​

归并排序 (Merge Sort) 适用于链表，因为：

  • 链表适合拆分（只需调整 next 指针）。
  • 链表合并两个有序链表很高效，可以用 O(1) 额外空间完成。

代码实现​

from typing import Optional

# 定义链表节点
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 递归终止条件
        if not head or not head.next:
            return head

        # 1. 使用快慢指针找到链表中点
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # 2. 断开链表，分成两个部分
        mid = slow.next
        slow.next = None  

        # 3. 递归排序两部分
        left = self.sortList(head)
        right = self.sortList(mid)

        # 4. 归并两个有序链表
        return self.merge(left, right)

    def merge(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        current = dummy
        
        while l1 and l2:
            if l1.val < l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
        
        # 连接剩余部分
        current.next = l1 if l1 else l2
        
        return dummy.next

# 测试代码
def print_list(head):
    """打印链表"""
    res = []
    while head:
        res.append(head.val)
        head = head.next
    print(res)

# 构造链表
head = ListNode(4, ListNode(2, ListNode(1, ListNode(3))))
solution = Solution()
sorted_head = solution.sortList(head)

print_list(sorted_head)  # 输出: [1, 2, 3, 4]

复杂度分析​

  • 时间复杂度：O(n log n)

    • find middle（快慢指针）需要 O(n)
    • merge 操作需要 O(n)
    • 递归深度为 log n，所以总时间复杂度 O(n log n)

  • 空间复杂度：O(log n) （递归栈深度）

    • 如果使用迭代归并排序，可以优化到 O(1)。

示例分析​

输入链表​

4 -> 2 -> 1 -> 3

归并排序过程​

  1. 找到中点，分为： 
    左：4 -> 2
    右：1 -> 3
  2. 递归排序左右： 
    左排序后：2 -> 4
    右排序后：1 -> 3
  3. 归并： 
    1 -> 2 -> 3 -> 4

最终输出​

1 -> 2 -> 3 -> 4

总结​

✅ 采用归并排序，符合 O(n log n) 要求。
✅ 使用快慢指针找中点，避免 O(n²) 的 length // 2 操作。
✅ 递归合并两个有序链表，符合链表结构特点。

这样，我们就高效地对链表进行了排序！🚀