Links

0147. 对链表进行插入排序

题目地址(147. 对链表进行插入排序)

https://leetcode-cn.com/problems/insertion-sort-list/

题目描述

对链表进行插入排序。
插入排序的动画演示如上。从第一个元素开始,该链表可以被认为已经部分排序(用黑色表示)。
每次迭代时,从输入数据中移除一个元素(用红色表示),并原地将其插入到已排好序的链表中。
 
插入排序算法:
插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
重复直到所有输入数据插入完为止。
 
示例 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)$。
大家对此有何看法,欢迎给我留言,我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库:https://github.com/azl397985856/leetcode 。 目前已经 38K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。