Scale Engineer

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:

  1. Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
  2. 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.
  3. 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.

/** * 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(0); // Dummy head for the sorted list        ListNode current = head; // Pointer to iterate through the original list         while (current != null) {            // Store the next node to process from the original list            ListNode nextNode = current.next;             // Find the correct position to insert 'current' in the sorted list            // We always start searching from the beginning of the sorted list            ListNode prev = dummy;            while (prev.next != null && prev.next.val < current.val) {                prev = prev.next;            }             // Insert 'current' between 'prev' and 'prev.next'            current.next = prev.next;            prev.next = current;             // Move to the next node in the original list            current = nextNode;        }         return dummy.next;    }}

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.

Solutions

/** * 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 ; } }

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 →

Next problem