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

Question

对链表进行插入排序。

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

插入排序算法：

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

示例 1：

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

示例 2：

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

---

思路

这道题属于链表题目中的修改指针。看过我链表专题的小伙伴应该熟悉我解决这种链表问题的套路了吧？

关于链表的题目，我总结了四个技巧虚拟头， 快慢指针，穿针引线 和 先穿再排后判空，这道题我们使用到了两个，分别是虚拟头和先穿再排后判空。

链表问题首先我们看返回值，如果返回值不是原本链表的头的话，我们可以使用虚拟节点。

此时我们的代码是这样的：

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        ans = ListNode(float("-inf"))
        # do domething
        return ans.next

接着，我们理清算法整体框架，把细节留出来。

我们的算法应该有两层循环，外层控制当前需要插入的元素，内层选择插入的位置。

此时我们的代码是这样的：

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        ans = ListNode(float("-inf"))

        def insert(to_be_insert):
            # 选择插入的位置，并插入

        while head:
            insert(head)
            head = head.next
        return ans.next

而选择插入位置的代码也不难，只需要每次都从头出发遍历，找到第一个大于 to_be_insert 的，在其前面插入即可（如果有的话）：

# ans 就是上面我提到的虚拟节点
ans = cur
while cur.next and cur.next.val < to_be_insert.val:
    cur = cur.next

而链表插入是一个基本操作，不多解释，直接看代码：

to_be_insert.next = cur.next
cur.next = to_be_insert

于是完整代码就呼之欲出了：

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        ans = ListNode(float("-inf"))

        def helper(inserted):
            cur = ans
            while cur.next and cur.next.val < inserted.val:
                cur = cur.next
            inserted.next = cur.next
            cur.next = inserted

        while head:
            helper(head)
            head = head.next
        return ans.next

到这里还没完，继续使用我的第二个技巧先穿再排后判空。由于这道题没有穿，我们直接排序和判空即可。

next 改变的代码一共两行，因此只需要关注这两行代码即可：

inserted.next = cur.next
cur.next = inserted

inserted 的 next 改变实际上会影响外层，解决方案很简单，留个联系方式就好。这我在上面的文章也反复提到过。

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
        ans = ListNode(float("-inf"))

        def insert(to_be_insert):
            # 选择插入的位置，并插入
            # 这里 to_to_insert 的 next 会被修改，进而影响外层的 head

        while head:
            # 留下联系方式
            next = head.next
            insert(head)
            # 使用联系方式更新 head
            head = next
        return ans.next

不熟悉这个技巧的看下上面提到的我写的链表文章即可。

如果你上面代码你会了，将 insert 代码整个复制出来就变成大部分人的解法了。不过我还是建议新手按照我的这个模式一步步来，稳扎稳打，不要着急。

代码

代码支持：Python3，Java，JS, CPP

Python Code:

class Solution:
    def insertionSortList(self, head: ListNode) -> ListNode:
       ans = ListNode(float("-inf"))

        while head:
            next = head.next
            cur = ans
            while cur.next and cur.next.val < head.val:
                cur = cur.next
            head.next = cur.next
            cur.next = head
            head = next
        return ans.next

Java Code:

class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode ans = new ListNode(-1);
        while( head != null ){
            ListNode next = head.next;
            ListNode cur = ans;
            while(cur.next != null && cur.next.val < head.val ){
                cur = cur.next;
            }
            head.next = cur.next;
            cur.next = head;
            head = next;
        }

        return ans.next;
    }
}

JS Code:

var insertionSortList = function (head) {
  ans = new ListNode(-1);
  while (head != null) {
    next = head.next;
    cur = ans;
    while (cur.next != null && cur.next.val < head.val) {
      cur = cur.next;
    }
    head.next = cur.next;
    cur.next = head;
    head = next;
  }

  return ans.next;
};

CPP Code:

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        ListNode dummy, *p;
        while (head) {
            auto *n = head;
            head = head->next;
            p = &dummy;
            while (p->next && p->next->val < n->val) p = p->next;
            n->next = p->next;
            p->next = n;
        }
        return dummy.next;
    }
};

复杂度分析

• 时间复杂度：$O(N^2)$，其中 N 为链表长度。
• 空间复杂度：$O(1)$。