第五章 - 高频考题（中等）
1906. 查询差绝对值的最小值
0147. 对链表进行插入排序
题目地址（147. 对链表进行插入排序）
题目描述
对链表进行插入排序。
1
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
2
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
3
4
5
6
插入排序算法：
7
8
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
9
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
10
重复直到所有输入数据插入完为止。
11
12
13
示例 1：
14
15
输入: 4->2->1->3
16
输出: 1->2->3->4
17
示例 2：
18
19
输入: -1->5->3->4->0
20
输出: -1->0->3->4->5
Copied!
思路
这道题属于链表题目中的修改指针。看过我链表专题的小伙伴应该熟悉我解决这种链表问题的套路了吧？
链表问题首先我们看返回值，如果返回值不是原本链表的头的话，我们可以使用虚拟节点。
此时我们的代码是这样的：
1
class Solution:
2
def insertionSortList(self, head: ListNode) -> ListNode:
3
ans = ListNode(float("-inf"))
4
# do domething
5
return ans.next
Copied!
接着，我们理清算法整体框架，把细节留出来。
我们的算法应该有两层循环，外层控制当前需要插入的元素，内层选择插入的位置。
此时我们的代码是这样的：
1
class Solution:
2
def insertionSortList(self, head: ListNode) -> ListNode:
3
ans = ListNode(float("-inf"))
4
5
def insert(to_be_insert):
6
# 选择插入的位置，并插入
7
8
while head:
9
insert(head)
10
head = head.next
11
return ans.next
Copied!
而选择插入位置的代码也不难，只需要每次都从头出发遍历，找到第一个大于 to_be_insert 的，在其前面插入即可（如果有的话）：
1
# ans 就是上面我提到的虚拟节点
2
ans = cur
3
while cur.next and cur.next.val < to_be_insert.val:
4
cur = cur.next
Copied!
而链表插入是一个基本操作，不多解释，直接看代码：
1
to_be_insert.next = cur.next
2
cur.next = to_be_insert
Copied!
于是完整代码就呼之欲出了：
1
class Solution:
2
def insertionSortList(self, head: ListNode) -> ListNode:
3
ans = ListNode(float("-inf"))
4
5
def helper(inserted):
6
cur = ans
7
while cur.next and cur.next.val < inserted.val:
8
cur = cur.next
9
inserted.next = cur.next
10
cur.next = inserted
11
12
while head:
13
helper(head)
14
head = head.next
15
return ans.next
Copied!
到这里还没完，继续使用我的第二个技巧先穿再排后判空。由于这道题没有穿，我们直接排序和判空即可。
next 改变的代码一共两行，因此只需要关注这两行代码即可：
1
inserted.next = cur.next
2
cur.next = inserted
Copied!
inserted 的 next 改变实际上会影响外层，解决方案很简单，留个联系方式就好。这我在上面的文章也反复提到过。
1
class Solution:
2
def insertionSortList(self, head: ListNode) -> ListNode:
3
ans = ListNode(float("-inf"))
4
5
def insert(to_be_insert):
6
# 选择插入的位置，并插入
7
# 这里 to_to_insert 的 next 会被修改，进而影响外层的 head
8
9
while head:
10
# 留下联系方式
11
next = head.next
12
insert(head)
13
# 使用联系方式更新 head
14
head = next
15
return ans.next
Copied!
不熟悉这个技巧的看下上面提到的我写的链表文章即可。
如果你上面代码你会了，将 insert 代码整个复制出来就变成大部分人的解法了。不过我还是建议新手按照我的这个模式一步步来，稳扎稳打，不要着急。
代码
代码支持：Python3，Java，JS, CPP
Python Code:
1
class Solution:
2
def insertionSortList(self, head: ListNode) -> ListNode:
3
ans = ListNode(float("-inf"))
4
5
while head:
6
next = head.next
7
cur = ans
8
while cur.next and cur.next.val < head.val:
9
cur = cur.next
10
head.next = cur.next
11
cur.next = head
12
head = next
13
return ans.next
Copied!
Java Code:
1
class Solution {
2
public ListNode insertionSortList(ListNode head) {
3
ListNode ans = new ListNode(-1);
4
while( head != null ){
5
ListNode next = head.next;
6
ListNode cur = ans;
7
while(cur.next != null && cur.next.val < head.val ){
8
cur = cur.next;
9
}
10
head.next = cur.next;
11
cur.next = head;
12
head = next;
13
}
14
15
return ans.next;
16
}
17
}
Copied!
JS Code:
1
var insertionSortList = function (head) {
2
ans = new ListNode(-1);
3
while (head != null) {
4
next = head.next;
5
cur = ans;
6
while (cur.next != null && cur.next.val < head.val) {
7
cur = cur.next;
8
}
9
head.next = cur.next;
10
cur.next = head;
11
head = next;
12
}
13
14
return ans.next;
15
};
Copied!
CPP Code:
1
class Solution {
2
public:
3
ListNode* insertionSortList(ListNode* head) {
4
ListNode dummy, *p;
5
while (head) {
6
auto *n = head;
7
head = head->next;
8
p = &dummy;
9
while (p->next && p->next->val < n->val) p = p->next;
10
n->next = p->next;
11
p->next = n;
12
}
13
return dummy.next;
14
}
15
};
Copied!
复杂度分析
- 时间复杂度：$O(N^2)$，其中 N 为链表长度。
- 空间复杂度：$O(1)$。
大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 38K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
最近更新 1yr ago