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.