147. Insertion Sort List

对链表进行插入排序。

插入排序的基本思想是，维护一个有序序列，初始时有序序列只有一个元素，每次将一个新的元素插入到有序序列中，将有序序列的长度增加1，直到全部元素都加入到有序序列中。

如果是数组的插入排序，则数组前面部分是有序序列，每次找到有序序列后面的第一个元素的插入位置，将有序序列中的插入位置后面的元素都往后移动一位。然后将待插入元素置于插入位置。

对于链表而言，插入元素只要更新相邻节点的指针即可，不需要像数组一样将插入位置后面的元素往后移动，因此插入操作的时间复杂度是 O(1)，但是找到插入位置 需要遍历链表中的节点，时间复杂度是O(n)，因此链表插入排序的总时间 复杂度是 O(n^2)

• 时间复杂度O(n^2)，空间复杂度O(1)
• Runtime: 143 ms, faster than 28.66%
• Memory Usage: 41.1 MB, less than 59.76%

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var insertionSortList = function(head) {
  if (!head) return head;
  let dummyHead = new ListNode(0);
  dummyHead.next = head;
  let lastSorted = head;
  let cur = head.next;
  while (cur) {
    if (lastSorted.val <= cur.val) {
      lastSorted = lastSorted.next;
    } else {
      let prev = dummyHead;
      while (prev.next.val <= cur.val) {
        prev = prev.next;
      }
      lastSorted.next = cur.next;
      cur.next = prev.next;
      prev.next = cur;
    }
    cur = lastSorted.next;
  }
  return dummyHead.next;
};