Insertion Sort List

Med

#0147Time: O(N^2)Space: O(1)1 company

Algorithms

Sorting

Data structures

Linked List

Companies

Google

Prompt

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

The steps of the insertion sort algorithm:

Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list and inserts it there.
It repeats until no input elements remain.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.

Example 1:

Input: head = [4,2,1,3]
Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]

Constraints:

The number of nodes in the list is in the range [1, 5000].
-5000 <= Node.val <= 5000

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly translates the insertion sort algorithm to a linked list. It builds a new sorted list by taking one node at a time from the original list and inserting it into its correct position in the new list. A dummy head is used to simplify the insertion logic, especially for inserting at the beginning of the sorted list.

Algorithm

Create a dummy node to serve as the head of the sorted list.
Initialize current = head to iterate through the input list.
Loop while current is not null:
- Store the next node: nextNode = current.next.
- Find the insertion point in the sorted list. Start a pointer prev = dummy.
- Traverse the sorted list: while (prev.next != null && prev.next.val < current.val) { prev = prev.next; }.
- Insert current after prev: current.next = prev.next; prev.next = current;.
- Move to the next node in the original list: current = nextNode;.
Return dummy.next.

Walkthrough

We initialize a dummy node that will act as a sentinel head for our new sorted list. This helps in handling insertions at the very beginning without special case logic.

We iterate through the original linked list using a current pointer, starting from the head. In each iteration, we "pick" the current node and find where it belongs in the sorted list (which is being built starting from dummy).

To find the insertion point, we use another pointer, prev, starting from dummy and traversing the sorted portion until we find the correct spot (prev.next == null or prev.next.val >= current.val). Once the position is found, we insert the current node after prev.

We must save the next node from the original list before we modify current.next for the insertion. This process is repeated until all nodes from the original list have been moved to the sorted list. Finally, we return dummy.next, which is the head of the fully sorted list.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode insertionSortList(ListNode head) {13        if (head == null || head.next == null) {14            return head;15        }16 17        ListNode dummy = new ListNode(0); // Dummy head for the sorted list18        ListNode current = head; // Pointer to iterate through the original list19 20        while (current != null) {21            // Store the next node to process from the original list22            ListNode nextNode = current.next;23 24            // Find the correct position to insert 'current' in the sorted list25            // We always start searching from the beginning of the sorted list26            ListNode prev = dummy;27            while (prev.next != null && prev.next.val < current.val) {28                prev = prev.next;29            }30 31            // Insert 'current' between 'prev' and 'prev.next'32            current.next = prev.next;33            prev.next = current;34 35            // Move to the next node in the original list36            current = nextNode;37        }38 39        return dummy.next;40    }41}

Complexity

Time

O(N^2)

Space

O(1)

Trade-offs

Pros

Simple to understand and implement.
Space-efficient as it only uses a constant amount of extra space.

Cons

Inefficient time complexity (O(N^2)), making it slow for large lists.
Performs poorly even on nearly sorted lists because it always scans the sorted part from the beginning.

This approach improves upon the simple insertion sort by adding a "fast path" optimization. It keeps track of the last element of the sorted portion of the list. If the next element to be inserted is greater than or equal to this last sorted element, it means the element is already in its correct relative position. In this case, we can simply extend the sorted portion in O(1) time without searching for an insertion point. If the element is smaller, we fall back to the standard procedure of searching from the beginning of the sorted list.

Algorithm

Handle the base case: if the list is empty or has one node, it's already sorted.
Create a dummy node and point its next to head.
Initialize lastSorted = head (the sorted part is just the first node).
Initialize current = head.next (the unsorted part starts from the second node).
Loop while current is not null:
- Fast Path: If current.val >= lastSorted.val:
  - lastSorted = lastSorted.next.
- Slow Path (Insertion needed): Else:
  - Find the insertion point prev by scanning from dummy.
  - Unlink current from the list: lastSorted.next = current.next.
  - Insert current after prev: current.next = prev.next; prev.next = current;.
- Move to the next unsorted node: current = lastSorted.next.
Return dummy.next.

Walkthrough

This method sorts the list in-place. We maintain a pointer, lastSorted, to the tail of the sorted prefix of the list, and a pointer current to the head of the remaining unsorted part. A dummy node is used to simplify insertions before the original head.

The main loop iterates as long as there are nodes in the unsorted part (current != null). Inside the loop, we first check if current.val is greater than or equal to lastSorted.val.

If it is, the current node is already in the correct position relative to the sorted prefix. We simply advance lastSorted to current and move on. This is the fast path.

If current.val is smaller, the node is out of order. We must find its correct place in the sorted prefix (dummy.next to lastSorted). To do this, we detach current from the list and scan from the dummy node to find the node prev after which current should be inserted. After insertion, current is updated to the next node in the unsorted part, which is now lastSorted.next.

This optimization significantly improves performance for lists that are already partially or fully sorted.

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode insertionSortList(ListNode head) {13        if (head == null || head.next == null) {14            return head;15        }16 17        ListNode dummy = new ListNode(0);18        dummy.next = head;19        20        ListNode lastSorted = head; // Tail of the sorted part21        ListNode current = head.next; // Node to be inserted22 23        while (current != null) {24            if (current.val >= lastSorted.val) {25                // Current node is already in its correct position26                lastSorted = lastSorted.next;27            } else {28                // Current node is smaller, need to find its insertion point29                // from the beginning of the sorted list.30                ListNode prev = dummy;31                while (prev.next.val < current.val) {32                    prev = prev.next;33                }34                35                // Unlink current from its original position36                lastSorted.next = current.next;37                38                // Insert current into the correct position39                current.next = prev.next;40                prev.next = current;41            }42            43            // Move to the next node to be sorted44            current = lastSorted.next;45        }46 47        return dummy.next;48    }49}

Complexity

Time

O(N^2) (Worst Case), O(N) (Best Case)

Space

O(1)

Trade-offs

Pros

More efficient than the simple version for nearly sorted lists.
Best-case time complexity is linear (O(N)).
Space-efficient.

Cons

Still has a quadratic (O(N^2)) worst-case time complexity.
The logic is slightly more complex than the simple version.

Solutions

Solution

1/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode insertionSortList ( ListNode head ) { if ( head == null || head . next == null ) { return head ; } ListNode dummy = new ListNode ( head . val , head ); ListNode pre = dummy , cur = head ; while ( cur != null ) { if ( pre . val <= cur . val ) { pre = cur ; cur = cur . next ; continue ; } ListNode p = dummy ; while ( p . next . val <= cur . val ) { p = p . next ; } ListNode t = cur . next ; cur . next = p . next ; p . next = cur ; pre . next = t ; cur = t ; } return dummy . next ; } }

1/** * Definition for singly-linked list. * function ListNode(val, next) { * this.val = (val===undefined ? 0 : val) * this.next = (next===undefined ? null : next) * } */ /** * @param {ListNode} head * @return {ListNode} */ var insertionSortList =2  function (head) {3    if (head == null || head.next == null) return head;4    let dummy = new ListNode(head.val, head);5    let prev = dummy,6      cur = head;7    while (cur != null) {8      if (prev.val <= cur.val) {9        prev = cur;10        cur = cur.next;11        continue;12      }13      let p = dummy;14      while (p.next.val <= cur.val) {15        p = p.next;16      }17      let t = cur.next;18      cur.next = p.next;19      p.next = cur;20      prev.next = t;21      cur = t;22    }23    return dummy.next;24  };

1# 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 : ListNode ) -> ListNode : if head is None or head . next is None : return head dummy = ListNode ( head . val , head ) pre , cur = dummy , head while cur : if pre . val <= cur . val : pre , cur = cur , cur . next continue p = dummy while p . next . val <= cur . val : p = p . next t = cur . next cur . next = p . next p . next = cur pre . next = t cur = t return dummy . next

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem