# Insertion Sort List

Sort a linked list using insertion sort.

We have explained Insertion Sort at Slide 7 of Arrays

Insertion Sort Wiki has some details on Insertion Sort as well.

Example :

```Input : 1 -> 3 -> 2

Return 1 -> 2 -> 3```
Method1:

Using the same implementation for sorting array.

Solution:

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

/**
* Definition for singly-linked list.
* class ListNode {
*     public int val;
*     public ListNode next;
*     ListNode(int x) { val = x; next = null; }
* }
*/
public class Solution {
// 3 2 1
// 2 3 1
public ListNode insertionSortList(ListNode A) {
if (A == null || A.next == null) return A;
int size = 0;
ListNode curr = A;
while (curr != null) {
size ++;
curr = curr.next;
}
int sortedSize = 1;
ListNode dummy = new ListNode(0);
dummy.next = A;
ListNode unsorted = A.next;
while (sortedSize < size) {
ListNode prev = dummy;
ListNode p = dummy.next;
ListNode unsortedNext = unsorted.next;
int s = 0;
while (s < sortedSize) {
ListNode next = p.next;
if (unsorted.val < p.val) {
prev.next = unsorted;
unsorted.next = p;
break;
}
prev = p;
p = next;
s ++;
if (s == sortedSize) {
prev.next = unsorted;
}
}
unsorted = unsortedNext;
sortedSize ++;
}
ListNode p = dummy;
int i = 0;
while (i < size) {
p = p.next;
i ++;
}
p.next = null;
return dummy.next;
}
}

Method 2:

Isolate the node. find the right place & insert. Continue from last sorted node.

Solution 2:

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

/**
* Definition for singly-linked list.
* class ListNode {
*     public int val;
*     public ListNode next;
*     ListNode(int x) { val = x; next = null; }
* }
*/
public class Solution {
private ListNode insert(ListNode node, ListNode start, ListNode end) {
ListNode p = start;
while (p.next != null && p.next.val < node.val && p != end) {
p = p.next;
}
node.next = p.next;
p.next = node;
return p == end ? node : end;
}

public ListNode insertionSortList(ListNode A) {
ListNode dummy = new ListNode(0);
ListNode prev = dummy;
ListNode unsorted = A;
while (unsorted != null) {
// isolate unsorted
prev.next = unsorted.next;
// sorted last node
prev = insert(unsorted, dummy, prev);
unsorted = prev.next;
}
return dummy.next;
}
}