⚡Flashcard Drill➔
NeetCode #331LC-148MediumLinked List
← Back to All Problems

#331 · #148 · Sort List(排序链表)

📌 Problem Statement & Constraints

Given the head of a linked list, sort it in ascending order and return the head. Constraints: the number of nodes is in [0, 5 * 10^4], -10^5 <= Node.val <= 10^5. The follow-up asks for O(n log n) time and O(1) space.

💡 Core Algorithmic Approaches

  1. Merge sort is the natural choice for linked lists: it is O(n log n), stable, and needs no random access.
  2. Split the list at the middle with slow/fast pointers, sever the link, and recursively sort both halves.
  3. Merge the two sorted halves with the standard two-pointer merge.
  4. The recursion depth is O(log n), so the space is O(log n) rather than O(1) -- which is the honest answer to the follow-up (a bottom-up merge sort achieves O(1)).

💻 Benchmark Python3 Implementation

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next:
            return head                    # 0 or 1 node -> already sorted
        # split at the middle (slow ends before the second half)
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        mid = slow.next
        slow.next = None                   # sever
        left = self.sortList(head)
        right = self.sortList(mid)
        # merge
        dummy = tail = ListNode(0)
        while left and right:
            if left.val <= right.val:      # '<=' keeps the sort stable
                tail.next = left
                left = left.next
            else:
                tail.next = right
                right = right.next
            tail = tail.next
        tail.next = left or right
        return dummy.next

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n): the recursion halves the list at each level and the merge is linear per level.
💾 Space Complexity
O(log n) for the recursion stack. A bottom-up merge sort would achieve O(1).

⚠️ Interview Pitfalls & Follow-ups

  • Starting fast at head instead of head.next: the split would be uneven and can cause infinite recursion on a two-node list.
  • Forgetting slow.next = None: the two halves would still be linked and the recursion would not terminate.
  • Using quick sort: pivot selection on a linked list is awkward and the worst case is O(n^2).
  • Copying values into an array and sorting: O(n) space and defeats the purpose.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems

中文速览与面试要点

排序链表

给你链表的头结点 head,请将其按 升序 排列并返回 排序后的链表 。进阶:你可以在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序吗?约束:链表中节点的数目在范围 [0, 5 × 10^4] 内;-10^5 ≤ Node.val ≤ 10^5。

核心要点

  • 归并排序(标准解,自上而下) :① 快慢指针找中点并断开;② 递归排序左右两半;③ 合并两个有序链表。
  • 为什么选归并而非快排 :链表不支持随机访问,快排的 partition 需要频繁访问中间元素;归并只需要顺序扫描,天然契合链表。
  • 复杂度 :每层合并 O(n),共 log n 层,总 O(n log n)。递归栈 O(log n)。
  • 自下而上的迭代归并(进阶) :先两两合并长度为 1 的段,再合并长度为 2 的段……可做到 O(1) 额外空间(不含输出)。

常见陷阱

  • 快指针的初值写成 head :会导致 slow 停在前半的最后一个节点 之后 ,中点划分错误。本解用 fast = head.next 让 slow 恰好停在前半最后一个节点。
  • 忘记 slow.next = None :两半仍相连,递归会无限进行。
  • 把链表值取出来排序后再重建 :可行且 O(n log n),但需要 O(n) 空间,且未利用链表特性。
  • 用冒泡或插入排序 :O(n²) 在 n = 5 × 10^4 时必然超时。
  • 递归深度 :O(log n),n = 5 × 10^4 时约 16 层,安全。

参考实现

class Solution:
    def sortList(self, head: 'ListNode') -> '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
        mid = slow.next
        slow.next = None                # 断开

        # ② 递归排序两半
        left = self.sortList(head)
        right = self.sortList(mid)

        # ③ 合并两个有序链表
        dummy = ListNode()
        tail = dummy
        while left and right:
            if left.val <= right.val:
                tail.next = left
                left = left.next
            else:
                tail.next = right
                right = right.next
            tail = tail.next
        tail.next = left or right
        return dummy.next