LeetCode #147 Medium

Insertion Sort List

Given the head of a singly linked list, sort it using insertion sort and return the sorted list's head.

linked-listsorting

02

Intuition

Insertion sort on a linked list is actually more natural than on an array, because inserting into the middle of a linked list is O(1) pointer surgery once you have found the position — no shifting needed. Maintain a sorted sub-list starting from a dummy head. For each node in the original list, detach it, scan the sorted sub-list to find where it belongs, and splice it in. The scan is the expensive part: O(n) per element in the worst case, giving O(n²) overall. But one optimisation helps: if the current node is already larger than the sorted tail, just append it — no scan needed. This handles already-sorted or nearly-sorted inputs in O(n).

How to spot this pattern

When a problem explicitly asks for insertion sort on a linked list, you must simulate the algorithm: for each element, find its place in the growing sorted prefix and splice it in. The linked list makes the splice cheap (no shifting), but the search for the insertion point is still O(n). The fast-path check against the sorted tail is a key optimisation for nearly-sorted inputs.

03

Approach

1

Detach each node from the unsorted remainder

Walk through the original list. For each node, save its next pointer (because you are about to redirect it), then detach it from the remaining list. This node will be inserted into the sorted sub-list.

2

Find the insertion point in the sorted sub-list

Starting from the sorted dummy head, advance a pointer until you find a node whose next value is greater than or equal to the current node's value. Insert the current node right after that pointer. An optimisation: keep a tail pointer for the sorted list. If the current value is >= tail.val, skip the scan and append directly to tail.

3

Splice the node in with two pointer assignments

Set current.next = prev.next and prev.next = current, where prev is the node just before the insertion point. This inserts current between prev and prev.next without shifting anything. After processing all nodes, dummy.next is the sorted head. Time is O(n²) worst case, O(n) best case (already sorted).

04

Solution

▶1class Solution:
▶2    def insertionSortList(self, head):
▶3        dummy = ListNode(0)
▶4        current = head
▶5        while current:
▶6            next_node = current.next
▶7            prev = dummy
▶8            while prev.next and prev.next.val < current.val:
▶9                prev = prev.next
▶10            current.next = prev.next
▶11            prev.next = current
▶12            current = next_node
▶13        return dummy.next

05

Common pitfalls

Not saving the next pointer before detaching the current node

✗ Wrong

current.next = prev.next
prev.next = current
current = current.next

✓ Right

next_node = current.next
current.next = prev.next
prev.next = current
current = next_node

Once you set current.next = prev.next, the original next pointer is lost. You cannot advance to the next unsorted node. Saving it first preserves the traversal.

Always scanning from the beginning of the sorted list

✗ Wrong

prev = dummy
while prev.next and prev.next.val < current.val:
    prev = prev.next

✓ Right

if current.val >= tail.val:
    tail.next = current
    tail = current
else:
    prev = dummy
    while prev.next.val < current.val:
        prev = prev.next
    current.next = prev.next
    prev.next = current

Without the tail optimisation, an already-sorted list triggers a full scan for every node — O(n²) even in the best case. Checking the tail first makes sorted inputs O(n).

Forgetting to null-terminate the sorted list's tail

✗ Wrong

# no explicit tail.next = None

✓ Right

tail.next = None  # after moving the last node

The last node appended to the sorted list might still point to its old successor in the unsorted list, creating a cycle. Explicitly setting tail.next = None after all insertions prevents this. In practice, the splice operations usually fix this, but it is safer to be explicit.

06

Edge cases

Empty list

Return None immediately.

Single node

Already sorted. The loop does not run, and the single node is returned.

Already sorted list

Every node is >= the sorted tail, so the fast-path append fires each time. No scanning needed — effectively O(n).

07

Complexity

Time

O(n²)

Space

O(1)

Worst case when the list is reverse-sorted. Best case O(n) for an already-sorted list with the tail optimisation.