【一天一大 lee】对链表进行插入排序 (难度:中等) - Day20201120

输入: 4->2->1->3
输出: 1->2->3->4

输入: 4->2->1->3
输出: 1->2->3->4

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var insertionSortList = function(head) {
    if (head === null) return head
    let _result = new ListNode(0),
        index = head, // 排序片段指针
        node = head.next // 遍历指针
    _result.next = head
    while (node) {
        // 遇到未排序节点（当前node为非排序节点）
        if (node.val < index.val) {
            const next = node
            // 将node拆除
            index.next = node.next
            // 从头遍历链表找插入位置
            let i = _result
            while (i.next) {
                if (i.next.val > node.val) {
                    // 插入节点node节点
                    node.next = i.next
                    i.next = node
                    break
                }
                i = i.next
            }
        } else {
            // 更新排序片段指针
            index = index.next
        }
        // 更新遍历的起点
        node = index.next
    }
    return _result.next
}