对链表进行插入排序

题目

给定单个链表的头 head, 使用插入排序对链表进行排序, 并返回排序后链表的头.

插入排序 算法的步骤:

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

下面是插入排序算法的一个图形示例.部分排序的列表(黑色)最初只包含列表中的第一个元素.每次迭代时, 从输入数据中删除一个元素(红色), 并就地插入已排序的列表中.

示例

输入: head = [-1, 5, 3, 4, 0]

输出: [-1, 0, 3, 4, 5]

题解

建立 dummy 节点的原因是: 快速排序可能会插入头部, 用 dummy 会让插入头部和其他位置操作一致

需要维护一个至今位置有序的节点. 叫做 lastSorted, 因为需要把当前元素 curr 插到前面有序链表中, 要将最后一个元素与 curr 后面的元素建立连接.

用以一个前驱节点 prev 来找到需要插入的位置, 找到第一个满足 prev.next.val >= curr.val 的前驱节点, 将 curr 插入其后面.

最后 curr 更新为 lastSorted 后面的元素, 即下一个需要进行插入排序的链表元素.

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

  const dummy = new ListNode(-1, head)
  let lastSorted = head
  let currr = head.next

  while (currr) {
    if (lastSorted.val <= currr.val) {
      lastSorted = lastSorted.next
    } else {
      let prev = dummy
      while (prev.next.val <= currr.val) {
        prev = prev.next
      }

      lastSorted.next = currr.next
      currr.next = prev.next
      prev.next = currr
    }

    currr = lastSorted.next
  }

  return dummy.next
}