7.12 Insertion Sort List

7.12.1 Problem Metadata

7.12.2 Description

Sort a singly linked lc-list using the insertion sort algorithm and return the head of the sorted lc-list.

7.12.3 Examples

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

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

7.12.4 Constraints

  • 0 <= n <= 5 * 10^4
  • -10^5 <= Node.val <= 10^5

7.12.5 Solution - Dummy Head Insertion

7.12.5.1 Walkthrough

Traverse the lc-list and insert each node into the correct position of a growing sorted prefix. A dummy head simplifies insertion at the front. For each node removed from the original lc-list, linearly search the sorted portion to place it where prev.val <= node.val < prev.next.val.

7.12.5.2 Analysis

  • Time Complexity: O(n^2) due to repeated linear scans for each insertion
  • Space Complexity: O(1) extra space

7.12.5.3 Implementation Steps

  1. Create dummy pointing to null; curr traverses the original lc-list.
  2. For each curr, remove it from the lc-list and find its insert location starting from dummy.
  3. Splice curr between prev and prev.next.
  4. Continue until all nodes are inserted; return dummy.next.

7.12.5.4 Code - Java

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        ListNode curr = head;

        while (curr != null) {
            ListNode next = curr.next;
            ListNode prev = dummy;
            while (prev.next != null && prev.next.val < curr.val) {
                prev = prev.next;
            }
            curr.next = prev.next;
            prev.next = curr;
            curr = next;
        }

        return dummy.next;
    }
}