{ }SolveLogs
⌕
Home / Linked List / #147
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.

Constraints
  • The number of nodes in the list is in the range [1, 5000].
  • -5000 <= Node.val <= 5000
linked-listsorting
Open on LeetCode ↗
02

Intuition

Insertion sort list sorts a linked list using insertion sort. The algorithm is familiar from arrays, and the interest here is entirely in the pointer manipulation. Insertion sort builds a sorted region one element at a time, scanning it to find where each new element belongs. On an array that scan runs backwards, shifting elements right to make room. A singly linked list has no backward pointers, so the scan must run forwards from the head each time: - For each node, walk the sorted portion from the front until finding the node it should follow, then splice it in. That forward scan is why this stays O(n²) — but unlike the array version, no shifting is needed. Insertion is a constant-time pointer update once the position is found. A dummy head node makes this tractable. Without one, inserting before the current first node is a special case requiring separate code; with one, every insertion is uniform, since every real node has a predecessor. The critical detail is saving curr.next before splicing. The splice overwrites curr.next, so without saving it first, the link to the remainder of the unsorted list is lost and the loop terminates early with a truncated result. A useful optimisation: if the current node is already larger than the tail of the sorted portion, it belongs at the end and no scan is needed. On nearly-sorted input this brings the cost close to O(n). Merge sort is the better algorithm for linked lists at O(n log n), but this problem specifically asks for insertion sort.

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

Try it first

Before reading on: price up what sorting first costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n²) time and O(1) space.

1

Scan forwards, not backwards

A singly linked list has no backward pointers, so the sorted region must be scanned from the head each time rather than walked backwards as in the array version.

2

Use a dummy head

Place a dummy node before the sorted list. Every real node then has a predecessor, making insertion before the first node an ordinary case rather than a special one.

3

Find the insertion point

Walk the sorted portion while the next node's value is smaller than the current node's. Stopping there gives the node the current one should follow.

4

Save the next pointer first

Store curr.next before splicing. The splice overwrites it, and losing it truncates the unsorted remainder — the defining bug of this problem.

5

Splice with two assignments

Point the current node at the successor, then point the predecessor at the current node. No shifting is needed, unlike the array version.

6

Skip the scan when already ordered

If the node exceeds the sorted tail, it belongs at the end. This brings nearly-sorted input close to O(n) at no cost to the general case.

7

Cost of the sort

Each insertion may scan the whole sorted region, giving O(n²) time with O(1) space. Merge sort achieves O(n log n) on lists, but this problem asks for insertion sort.

04

Solution & live demo

▶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.
← Prev · #146
LRU Cache
Next · #148 →
Sort List