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
- Merge sort is the natural choice for linked lists: it is O(n log n), stable, and needs no random access.
- Split the list at the middle with slow/fast pointers, sever the link, and recursively sort both halves.
- Merge the two sorted halves with the standard two-pointer merge.
- 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
fastatheadinstead ofhead.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.
🧩 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