Sort a linked list using insertion sort.
Initial Though
這題很有意思， insertion sort 可能是大家最熟悉的 n^2 sorting ， 原本認為用 array 來作 insert 要花很多時間在做資料搬移，但當做在單向的 LinkedList 卻用變得更棘手。
Guide
第一個遇到的問題就是要 maintain 前後兩個 node 的 next 要能指對。所以當有一個直鏈：A->B->C 若要用 D 取代 B 我就要確保 A->D 和 D->C 。 這個可以用一個暫存的 Object pre 來儲存。第二個問題就是 head 是沒有 parent ， 所以要用一個空的dummy_head 來當作假的 head。 最後就是這題用一個很不像傳統 insertion sort 的解法，也就是分成兩個鏈，一個是 dummy 開頭的 sorted 鏈 ， 一個就是原本 input 進來的鏈。所以每次從 input 鏈抓一個 node cur ， 然後到 sorted 鏈裡找到是適合的地方插進去，這樣的作法會比用同一條鏈還 maintain 兩個鏈來的容易很多。
Code
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
ListNode dummy_head = new ListNode(0);
public ListNode insertionSortList(ListNode head) {
if(head == null)
return head;
ListNode pre,cur,iter;
cur = head;
while(cur !=null){
iter = dummy_head;
while(iter.next!=null && iter.next.val < cur.val){
iter= iter.next;
}
pre = cur.next;
cur.next = iter.next;
iter.next = cur;
cur = pre;
}
return dummy_head.next;
}
}