Insertion Sort List

Sort a linked list using insertion sort.

Analysis

1. 遍历每一个node
2. 对每一个node，再从头遍历，找出要插入的地方(注意要找到插入的前一个点)
3. 由于头可能会变，所以要有dummy head

Code

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode dummy = new ListNode(0);

        ListNode cur = head;
        while (cur != null) {
            ListNode pre = dummy;
            while (pre.next != null && pre.next.val < cur.val) {
                pre = pre.next;
            }
            ListNode temp = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            cur = temp;
        }

        return dummy.next;
    }
}

Notes

1. How to use dummy is new here.
2. 每一次从之前的list里面找curr node，插入到新的dummy开头的list。
3. temp用来指向剩下的没有整理的nodes，和dummy指向的list是分开的两个list。
4. 如果一开始dummy.next指向head的话，就会有looped list。

Reference

Ref1: Yu sorting algorithms
Ref2