> For the complete documentation index, see [llms.txt](https://zedive.gitbook.io/project-l/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://zedive.gitbook.io/project-l/part-1/basic_data_structure/linked_list/singly-linked-list/insertion-sort-list.md).

# Insertion Sort List

## Question ([LC.147](https://leetcode.com/problems/insertion-sort-list/))

> Sort a linked list using insertion sort.

## Example

```
3 -> 2 -> 5 -> null
2 -> 3 -> 5 -> null
```

## Analysis

```
Insertion Sort
dummy node

for each node in the linked list
    insert the node into the sorted position
end for

return dummy.next;

Insert
stop when the next node.value > newNode.value
Node temp = travel.next;
travel.next = newNode;
newNode.next = temp;
```

## Code

```java
public ListNode insertionSortList(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }

    ListNode dummy = new ListNode(Integer.MIN_VALUE);
    ListNode travel = head;

    while (travel != null) {
        ListNode temp = travel.next;
        insert(dummy, travel);
        travel = temp;
    }

    return dummy.next;
}

// assume head is not null
private void insert(ListNode head, ListNode newNode) {
    ListNode travel = head;

    while (travel.next != null && travel.next.val < newNode.val) {
        travel = travel.next;
    }

    ListNode temp = travel.next;
    travel.next = newNode;
    newNode.next = temp;
}
```