# 0147. 对链表进行插入排序
### 题目地址（147. 对链表进行插入排序）
### 题目描述
对链表进行插入排序。
```
插入排序的动画演示如上。从第一个元素开始，该链表可以被认为已经部分排序（用黑色表示）。
每次迭代时，从输入数据中移除一个元素（用红色表示），并原地将其插入到已排好序的链表中。
插入排序算法：
插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。
示例 1：
输入: 4->2->1->3
输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0
输出: -1->0->3->4->5
```
### 思路
这道题属于链表题目中的修改指针。看过我链表专题的小伙伴应该熟悉我解决这种链表问题的套路了吧？
关于链表的题目，我总结了四个技巧**虚拟头**， **快慢指针**，**穿针引线** 和 **先穿再排后判空**，这道题我们使用到了两个，分别是**虚拟头**和**先穿再排后判空**。这四个技巧的具体内容可以查看我的[《链表专题》](https://lucifer.ren/blog/2020/11/08/linked-list/)。
链表问题首先我们看返回值，如果返回值不是原本链表的头的话，我们可以使用虚拟节点。
此时我们的代码是这样的：
```py
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
ans = ListNode(float("-inf"))
# do domething
return ans.next
```
接着，我们理清算法整体框架，把细节留出来。
我们的算法应该有两层循环，外层控制当前需要插入的元素，内层选择插入的位置。
此时我们的代码是这样的：
```py
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 的，在其前面插入即可（如果有的话）：
```py
# ans 就是上面我提到的虚拟节点
ans = cur
while cur.next and cur.next.val < to_be_insert.val:
cur = cur.next
```
而链表插入是一个基本操作，不多解释，直接看代码：
```py
to_be_insert.next = cur.next
cur.next = to_be_insert
```
于是完整代码就呼之欲出了：
```py
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 改变的代码一共两行，因此只需要关注这两行代码即可：
```py
inserted.next = cur.next
cur.next = inserted
```
inserted 的 next 改变实际上会影响外层，解决方案很简单，**留个联系方式**就好。这我在上面的文章也反复提到过。
```py
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:
```py
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:
```java
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:
```js
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:
```cpp
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 题解仓库： 。 目前已经 38K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。
---
# Agent Instructions: Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.
Perform an HTTP GET request on the current page URL with the `ask` query parameter:
```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/medium/147.insertion-sort-list.md?ask=
```
The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.
Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.