147. Insertion Sort List

Sort a linked list using insertion sort.
使用插入排序法排链表。

var insertionSortList = function(head) {
    if( head === null ){
        return head;
    }
    //假的头节点
    var dummyHead = new ListNode(); 
    //本次需要被排序的节点
    var cur = head; 
    //本次被排序的节点将被插入pre和pre.next之间
    var pre = dummyHead; 
    //下次需要被排序的节点
    var next = null; 
    //判断是否到尾部
    while( cur !== null ){
        next = cur.next;
        //找到pre
        //当pre已经是最后一个了，说明已经到达有序区尾部
        //或者当找到pre.next大于等于cur.val，说明cur应该插在pre后
        while( pre.next !== null && pre.next.val < cur.val ){
            pre = pre.next;
        }
        //插入pre与pre.next之间
        cur.next = pre.next;
        pre.next = cur;
        pre = dummyHead;
        cur = next;
    }
    return dummyHead.next;
};