Insertion Sort List

How it works

This is the classic insertion sort adapted for linked lists. Instead of swapping values, we physically remove a node and reinsert it at the correct position in the already sorted portion. A dummy node simplifies insertions at the head. If the current node is already in order relative to the previous node, we just advance. Otherwise, we unlink it and search from the beginning for the right spot.

Steps

1. Create a dummy node pointing to the head to handle edge cases.
2. Maintain prev as the last node of the sorted portion and cur as the node being examined.
3. If cur.val >= prev.val, the node is in place; advance both pointers.
4. Otherwise, find the correct insertion point by scanning from the dummy:
   • Unlink cur from its current position.
   • Insert cur after the found position.
   • Update cur to prev.next to continue.
5. Return dummy.next.

Complexity

• Time complexity: O(n ^ 2)
• Space complexity: O(1) extra space.

Things to watch for

Losing Track of the Next Node Before Unlinking

When removing a node from its current position to reinsert it elsewhere, failing to save cur.next before modifying pointers causes the reference to the next node to be lost. Always store the next node in a temporary variable before performing any pointer manipulation.

Not Using a Dummy Node for Head Insertions

When the smallest element is found later in the list and needs to become the new head, not using a dummy node makes head updates awkward and error-prone. A dummy node pointing to the head simplifies insertions at the beginning by providing a consistent previous node.

Incorrectly Advancing Pointers After Insertion

After inserting a node into its correct sorted position, the prev pointer should not advance because the node that was after cur is now directly after prev. Advancing prev would skip a node. Only cur should be updated to prev.next to continue with the next unsorted element.

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        prev, cur = head, head.next

        while cur:
            if cur.val >= prev.val:
                prev, cur = cur, cur.next
                continue

            tmp = dummy
            while cur.val > tmp.next.val:
                tmp = tmp.next

            prev.next = cur.next
            cur.next = tmp.next
            tmp.next = cur
            cur = prev.next

        return dummy.next

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* prev = head;
        ListNode* cur = head->next;

        while (cur) {
            if (cur->val >= prev->val) {
                prev = cur;
                cur = cur->next;
                continue;
            }

            ListNode* tmp = dummy;
            while (tmp->next->val < cur->val) {
                tmp = tmp->next;
            }

            prev->next = cur->next;
            cur->next = tmp->next;
            tmp->next = cur;
            cur = prev->next;
        }

        return dummy->next;
    }
};