147.对链表进行插入排序

题目描述

给定单个链表的头 head ，使用插入排序对链表进行排序，并返回排序后链表的头。
插入排序步骤如下：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

Alt text

思路

迭代链表当 cur.val < cur.next.val 时不需要交换
反之需要执行交换逻辑了
把需要交换的节点 cur.next 保存到 temp 上，然后把 cur.next 从链表上删除
执行查找插入位置逻辑

// 从头开始遍历找到该插入的位置
prev = dummyHead;
while (prev.next.val <= temp.val) {
  prev = prev.next;
}

执行插入操作

// 执行插入操作
temp.next = prev.next;
prev.next = temp;

代码

/**
 * 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 === null) return null;
  let dummyHead = new ListNode(0);
  dummyHead.next = head;
  let temp = null;
  let prev = null;
  let cur = dummyHead.next;
  while (cur && cur.next) {
    if (cur.val <= cur.next.val) {
      cur = cur.next;
    } else {
      temp = cur.next; // 保存将要重新插入排序的节点
      cur.next = cur.next.next; // 删除当前节点

      // 从头开始遍历找到该插入的位置
      prev = dummyHead;
      while (prev.next.val <= temp.val) {
        prev = prev.next;
      }
      // 执行插入操作
      temp.next = prev.next;
      prev.next = temp;
    }
  }
  return dummyHead.next;
};

147.对链表进行插入排序 ​

题目描述 ​

思路 ​

代码 ​

147.对链表进行插入排序

题目描述

思路

代码