# Insertion Sort List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/insertion-sort-list)
Canonical: https://scaleengineer.com/dsa/problems/insertion-sort-list
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Linked List
**Companies:** [Google](https://scaleengineer.com/companies/google)
---
## Problem
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.

![](https://assets.glich.co/dsa/insertion-sort-list/image0.gif) 

**Example 1:**

![](https://assets.glich.co/dsa/insertion-sort-list/image1.jpg) 

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

**Example 2:**

![](https://assets.glich.co/dsa/insertion-sort-list/image2.jpg) 

**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
## Simple Insertion Sort
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.
**Time:** O(N^2) · **Space:** O(1)
**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.
### Explanation
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.

```java
/**
 * 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;
    }
}
```
### 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`.

## Optimized Insertion Sort with Fast Path
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.
**Time:** O(N^2) (Worst Case), O(N) (Best Case) · **Space:** O(1)
**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.
### Explanation
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.

```java
/**
 * 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.next = head;
        
        ListNode lastSorted = head; // Tail of the sorted part
        ListNode current = head.next; // Node to be inserted

        while (current != null) {
            if (current.val >= lastSorted.val) {
                // Current node is already in its correct position
                lastSorted = lastSorted.next;
            } else {
                // Current node is smaller, need to find its insertion point
                // from the beginning of the sorted list.
                ListNode prev = dummy;
                while (prev.next.val < current.val) {
                    prev = prev.next;
                }
                
                // Unlink current from its original position
                lastSorted.next = current.next;
                
                // Insert current into the correct position
                current.next = prev.next;
                prev.next = current;
            }
            
            // Move to the next node to be sorted
            current = lastSorted.next;
        }

        return dummy.next;
    }
}
```
### 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`.

# Solutions
### Java

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

### JavaScript

```javascript
/** * 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 =
  function (head) {
    if (head == null || head.next == null) return head;
    let dummy = new ListNode(head.val, head);
    let prev = dummy,
      cur = head;
    while (cur != null) {
      if (prev.val <= cur.val) {
        prev = cur;
        cur = cur.next;
        continue;
      }
      let p = dummy;
      while (p.next.val <= cur.val) {
        p = p.next;
      }
      let t = cur.next;
      cur.next = p.next;
      p.next = cur;
      prev.next = t;
      cur = t;
    }
    return dummy.next;
  };

```

### Python

```python
# 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
```