147. 对链表进行插入排序

题目

插入排序算法：

1. 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
2. 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
3. 重复直到所有输入数据插入完为止。

题解

模拟

/**
 * 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) return head;
  let node = head.next;
  let tail = head; // 已排序链表的尾节点

  while (node) {
    const next = node.next;
    // 要插入的节点小于已排序链表的头节点
    // 直接插入到头节点之前
    // 然后替换头节点
    // 这种情况尾节点不变
    if (node.val < head.val) {
      node.next = head;
      head = node;
    } else if (node.val >= tail.val) {
      // 要插入节点大于尾节点
      // 插入节点变为尾节点
      tail = node;
    } else {
      // 如果不是就遍历已排序链表找到位置插入
      let n = head;
      let m = n.next;
      while (m.val < node.val) {
        m = m.next;
        n = n.next;
      }
      n.next = node;
      node.next = m;
    }
    tail.next = next;
    node = tail.next;
  }
  return head;
};

插入排序

/**
 * 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 null;

  // 添加虚拟头节点方便头节点前面插入
  let fakehead = new ListNode(0);
  fakehead.next = head;

  // 最后一个有序节点
  let lastIndex = head;

  // 当前插入节点
  let cur = head.next;

  while (cur) {
    // 如果下个插入的节点也是有序的就继续
    if (cur.val >= lastIndex.val) {
      lastIndex = lastIndex.next;
    } else {
      // 否则从头开始查找插入位置
      let prev = fakehead;
      while (prev.next.val <= cur.val) {
        prev = prev.next;
      }
      lastIndex.next = cur.next;
      cur.next = prev.next;
      prev.next = cur;
    }
    cur = lastIndex.next;
  }

  return fakehead.next;
};