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
- Maintain a sorted prefix starting at a dummy head.
- For each node in the original list, scan the sorted prefix for the first node whose value exceeds it, and insert before that node.
- Because the prefix is sorted, the scan stops early in the average case -- but the worst case is still O(n^2).
- 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.nextbefore 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.