⚡Flashcard Drill➔
NeetCode #336LC-147MediumLinked List
← Back to All Problems

#336 · #147 · Insertion Sort List(对链表进行插入排序)

📌 Problem Statement & Constraints

Given the head of a singly linked list, sort it using insertion sort and return the head. The steps of the insertion sort must be represented by relinking the nodes. Constraints: 1 <= n <= 5000, -5000 <= Node.val <= 5000.

💡 Core Algorithmic Approaches

  1. Maintain a sorted prefix starting at a dummy head.
  2. For each node in the original list, scan the sorted prefix for the first node whose value exceeds it, and insert before that node.
  3. Because the prefix is sorted, the scan stops early in the average case -- but the worst case is still O(n^2).
  4. The dummy head removes the special case of inserting at the front.

💻 Benchmark Python3 Implementation

class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        cur = head
        while cur:
            prev = dummy
            # find the first node in the sorted prefix with a greater value
            while prev.next and prev.next.val <= cur.val:
                prev = prev.next
            nxt = cur.next             # save before relinking
            cur.next = prev.next
            prev.next = cur
            cur = nxt
        return dummy.next

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n^2) in the worst case (a reverse-sorted list), O(n) on an already-sorted list.
💾 Space Complexity
O(1): the nodes are relinked in place.

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting to save cur.next before relinking: the rest of the input list would be lost.
  • Using prev.next.val < cur.val: the comparison must be <= to keep the sort stable.
  • Creating new nodes: the problem expects the existing nodes to be rearranged.
  • Expecting O(n log n): insertion sort is inherently O(n^2) worst case; the problem asks for insertion sort specifically, which is why this variant exists alongside Sort List.
⚡
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