Insertion Sort List

1. Define the problem

Given the head of a singly linked list , sort the list using insertion sort , and return the sorted list. Remove one node at a time from the original list and insert it into the correct position of a new sorted list, by relinking pointers instead of comparing array indices.

Constraints

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

Example

Inputhead = [4, 2, 1, 3]

Output[1, 2, 3, 4]

Explanation Each node is removed from the original list and inserted into the sorted list at its correct spot.

2. Know the words first

In plain terms

Linked list: A chain of items where each item points to the next one, like a scavenger hunt where each clue tells you where to find the next.

3. Visualize the solution

Remove one node at a time, insert it into the sorted list

sorted—

Statusinit

Original list: 4 → 2 → 1 → 3. The sorted list starts empty, so all four slots show —.

What happens in this step

original list: 4 → 2 → 1 → 3
sorted list: (empty)

The original list will be consumed one node at a time; the sorted list grows from nothing. The row below is that sorted list — four slots, all empty for now.

Step 1 of 5

Steps to visualize

Keep a dummy head in front of a growing sorted list.
The row is the sorted list, four slots wide. A slot marked — is not filled yet.
Take the next node from the original list.
Walk the sorted list from the front until you find where the node belongs.
Relink pointers to splice the node into that spot.
Repeat until every node from the original list has been moved.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Remove one node at a time, insert it into the sorted list

sorted—

Statusinit

Original list: 4 → 2 → 1 → 3. The sorted list starts empty, so all four slots show —.

What happens in this step

original list: 4 → 2 → 1 → 3
sorted list: (empty)

The original list will be consumed one node at a time; the sorted list grows from nothing. The row below is that sorted list — four slots, all empty for now.

Step 1 of 5

5. Solution

Solution

solution.tsTypeScript

function insertionSortList(values) {
  function buildList(arr) {
    const dummy = { val: 0, next: null };
    let curr = dummy;
    for (const v of arr) {
      curr.next = { val: v, next: null };
      curr = curr.next;
    }
    return dummy.next;
  }

  function toArray(head) {
    const result = [];
    let node = head;
    while (node) {
      result.push(node.val);
      node = node.next;
    }
    return result;
  }

  const head = buildList(values);
  if (!head) {
    return [];
  }

  const dummy = { val: 0, next: null };
  let curr = head;

  while (curr) {
    const next = curr.next;
    let prev = dummy;

    while (prev.next && prev.next.val < curr.val) {
      prev = prev.next;
    }

    curr.next = prev.next;
    prev.next = curr;
    curr = next;
  }

  return toArray(dummy.next);
}

Time: O(n^2)
Space: O(1)

6. Test cases

Test cases

Input	Expected	Covers
`head = [4, 2, 1, 3]`	`[1, 2, 3, 4]`	example from the docstring
`head = [1, 2, 3, 4]`	`[1, 2, 3, 4]`	list is already sorted
`head = [5, 4, 3, 2, 1]`	`[1, 2, 3, 4, 5]`	worst case, every node inserts at the very front
`head = [1]`	`[1]`	smallest valid input, a single node
`head = [3, 1, 2, 1]`	`[1, 1, 2, 3]`	repeated values, stability keeps insertion correct
`head = [0, -2, 3, -1]`	`[-2, -1, 0, 3]`	negative and positive values mixed together
`head = [2, 1]`	`[1, 2]`	boundary case, exactly two nodes out of order

Insertion Sort List