⚡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