# [LeetCode 147] Insertion Sort List

### Question

Sort a linked list using insertion sort.

### Stats

 Adjusted Difficulty 3 Time to use --------

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

### Analysis

This question is a little tricky, but not difficult. First important thing is to konw what is insertion sort. It is always keeping a sorted list, and then get next unsorted element and insert into correct position of the sorted list.

### Solution

Almost all solutions on internet is same, so I will just explain my code. My code can be optimized a little bit by studying this blog, but I guess it’s just refactoring 1 or 2 variables and execution time would not be affected.

My solution is dividing the list into 2 parts: sorted part and unsorted part. I keep getting next node from unsorted and insert into sorted.

### My code

Recursion:

``````public ListNode insertionSortList(ListNode head) {
ListNode sorted = new ListNode(Integer.MIN_VALUE);
// the sorted and unsort both are not null at this point
while (unsort != null) {
ListNode pos = sorted;
ListNode cur = unsort;
unsort = unsort.next;
while (pos.next != null && pos.val < cur.val
&& pos.next.val < cur.val) pos = pos.next;
// now insert (cur) to (pos.next)
cur.next = pos.next;
pos.next = cur;
}
return sorted.next;
}
``````

Updated on June 17th, rewrote the code with dummy head. This is different solution, with better readability.

``````public ListNode insertionSortList(ListNode head) {
return null;
}
ListNode dummy = new ListNode(0);
while (cur != null) {
// insert cur into correct pos
ListNode pos = dummy;
while (pos.next != null && pos.next.val < cur.val) {
pos = pos.next;
}
ListNode temp = cur.next;
cur.next = pos.next;
pos.next = cur;
cur = temp;
}
return dummy.next;
}
``````