1. 题目描述

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

插入排序算法：

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

  3. 重复直到所有输入数据插入完为止。


    示例 1：

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

    示例 2：

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

    2. 解题思路

    对于单向链表而言，只有指向后一个节点的指针，因此需要从链表的头节点开始往后遍历链表中的节点，寻找插入位置。对链表进行插入排序的具体过程如下:

  4. 首先判断给定的链表是否为空，若为空，则不需要进行排序，直接返回。

  5. 创建哑节点 dummyHead，令 dummyHead.next = head。引入哑节点是为了便于在 head 节点之前插入节点。
  6. 维护 last 为链表的已排序部分的最后一个节点，初始时 last = head。
  7. 维护 cur 为待插入的元素，初始时 cur = head.next。
  8. 比较 last 和 cur 的节点值。
  • 若 last.val <= cur.val，说明 cur 应该位于 last 之后，将 last后移一位，curr 变成新的 last。
  • 否则，从链表的头节点开始往后遍历链表中的节点，寻找插入 cur 的位置。令 pre 为插入 cur 的位置的前一个节点，进行如下操作，完成对 cur 的插入：
    1. last.next = cur.next
    2. cur.next = pre.next
    3. pre.next = cur
  1. 令 cur = last.next，此时 cur 为下一个待插入的元素。
  2. 重复第 5 步和第 6 步，直到 cur 变成空，排序结束。
  3. 返回 dummyHead.next，为排序后的链表的头节点。

复杂度分析：

  • 时间复杂度：O(n2)，对于链表而言，插入元素时只要更新相邻节点的指针即可，因此插入操作的时间复杂度是 O(1)，但是找到插入位置需要遍历链表中的节点，时间复杂度是 O(n)，因此链表插入排序的总时间复杂度仍然是 O(n)，其中 n 是链表的长度。

  • 空间复杂度：O(1)，需要额外的常数大小的辅助空间。

    3. 代码实现

    1. /**
    2. * Definition for singly-linked list.
    3. * function ListNode(val, next) {
    4. *     this.val = (val===undefined ? 0 : val)
    5. *     this.next = (next===undefined ? null : next)
    6. * }
    7. */
    8. /**
    9. * @param {ListNode} head
    10. * @return {ListNode}
    11. */
    12. var insertionSortList = function(head) {
    13.   if(!head){
    14.       return head
    15.   }
    16.   const dummyHead = new ListNode(0)
    17.   dummyHead.next = head
    19.   let last = head, cur = head.next
    21.   while(cur){
    22.       if(last.val <= cur.val){
    23.           last = last.next
    24.       }else{
    25.           let pre = dummyHead
    26.           while(pre.next.val <= cur.val){
    27.               pre = pre.next
    28.           }
    29.           last.next = cur.next
    30.           cur.next = pre.next
    31.           pre.next = cur
    32.       }
    33.       cur = last.next
    34.   }
    35.   return dummyHead.next
    36. };

    4. 提交结果

    image.png