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) {
if (head == null || head.next == null) return head;
ListNode sorted = new ListNode(Integer.MIN_VALUE);
sorted.next = head;
ListNode unsort = head.next;
head.next = null;
// 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) {
if (head == null) {
return null;
}
ListNode dummy = new ListNode(0);
ListNode cur = head;
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;
}