147. 对链表进行插入排序 | LeetCode算法题解

题目描述

对链表进行插入排序。

插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。

示例 1:

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

示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

来源：LeetCode

思路

维护两个链表，已排序的和待排序的，将待排序的的节点依次插入到已排序链表就可以了。

需要特别注意的是插入的情况，分为在头部、非头部两种情况，稍不注意就容易空指针异常。

解法

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
const insertionSortList = head => {
  let sorted = null; // 已排序
  let pending = head; // 待排序

  // 把待pending的节点一个个插入到sorted
  while (pending) {
    const node = pending;
    pending = pending.next;
    node.next = null;

    // 寻找插入点
    let p = sorted;
    let q = null; // p的前一个节点
    while (p && node.val > p.val) {
      q = p;
      p = p.next;
    }

    if (!q) {
      node.next = sorted;
      sorted = node;
    } else {
      q.next = node;
      node.next = p;
    }
  }

  return sorted;
};