02、对链表进行插入排序
大约 6 分钟数据结构算法算法基地面试刷题
题目描述
有的老哥说链表的排序搞不明白，让我写一下，一不小心给忘记了，今天咱们就安排上。没有学过数据结构的同学可以先看下链表相关的文章
另外大家如果忘记了插入排序和归并思想的话，可以看之前的文章先复习一下，不然这两道题目会看得云里雾里。
示例 1：
输入: 4->2->1->3 输出: 1->2->3->4
示例 2：
输入: -1->5->3->4->0 输出: -1->0->3->4->5
题目解析
下面咱们先来看个动画回忆一下插入排序的具体执行步骤，然后我们再来说下面的题目。
我们的指针在数组时，可以随意的前后移动，将指针指向值和新元素的值比较后，将新元素插入到合适的位置。
我们知道链表查询元素的时间复杂度为 O(n)，我们只能够通过遍历链表查询元素。
那么我们怎么才能将新元素放到合适的位置呢？见下图。
此时我们不能通过移动绿色指针来寻找 5 的合适位置，那么我们应该怎么做呢？见下图。
当我们发现绿色指针的值大于新元素时（7 > 5），我们则可以定义一个新指针，让其从哑节点开始遍历，直到找到新元素（5）的位置，（4 和 7 之间），然后再将新元素插入即可。
我们是通过下面这行代码来找到插入位置的, temphead 则代表我们的紫色指针。
while (temphead.next.val <= pre.val) {
temphead = temphead.next;
}
下面我们再来看动画模拟具体过程。
注：为了更好的表达算法思想，让过程更流畅，特省略了指针的移动细节，直接插入到合适位置，后面会详细说明插入操作的具体步骤。
我们通过上面的动画知道了大致过程，那么我们的是如何将新元素插入到指定位置的呢？
见下图。
我们想要将 3 插入到 2 和 4 的中间，此时我们三个指针分别指向 2，4，3。
我们共分 4 步，来完成这个操作，见下图。
我们来把上图中的最后结果来捋一下看看最后结果是不是完成了插入操作。
这样我们就完成了链表的插入排序。下面我们来看下题目代码吧。
代码
Java Code:
class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null && head.next == null) {
return head;
}
//哑节点
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
//pre负责指向新元素，last 负责指向新元素的前一元素
//判断是否需要执行插入操作
ListNode pre = head.next;
ListNode last = head;
while (pre != null) {
//不需要插入到合适位置，则继续往下移动
if (last.val <= pre.val) {
pre = pre.next;
last = last.next;
continue;
}
//开始出发，查找新元素的合适位置
ListNode temphead = dummyNode;
while (temphead.next.val <= pre.val) {
temphead = temphead.next;
}
//此时我们已经找到了合适位置，我们需要进行插入，大家可以画一画
last.next = pre.next;
pre.next = temphead.next;
temphead.next = pre;
//继续往下移动
pre = last.next;
}
return dummyNode.next;
}
}
C++ Code:
class Solution {
public:
ListNode* insertionSortList(ListNode* head) {
if (head == nullptr && head->next == nullptr) {
return head;
}
//哑节点
ListNode * dummyNode = new ListNode(-1);
dummyNode->next = head;
//pre负责指向新元素，last 负责指向新元素的前一元素
//判断是否需要执行插入操作
ListNode * pre = head->next;
ListNode * last = head;
while (pre != nullptr) {
//不需要插入到合适位置，则继续往下移动
if (last->val <= pre->val) {
pre = pre->next;
last = last->next;
continue;
}
//开始出发，查找新元素的合适位置
ListNode * temphead = dummyNode;
while (temphead->next->val <= pre->val) {
temphead = temphead->next;
}
//此时我们已经找到了合适位置，我们需要进行插入，大家可以画一画
last->next = pre->next;
pre->next = temphead->next;
temphead->next = pre;
//继续往下移动
pre = last->next;
}
return dummyNode->next;
}
};
JS Code:
var insertionSortList = function (head) {
if (head === null || head.next === null) return head;
//哑节点
let dummyNode = new ListNode(-1, head);
let pre = head.next;
//pre负责指向新元素，last 负责指向新元素的前一元素
//判断是否需要执行插入操作
let last = head;
while (pre) {
//不需要插入到合适位置，则继续往下移动
if (last.val <= pre.val) {
last = last.next;
pre = pre.next;
continue;
}
//开始出发，查找新元素的合适位置
let tempHead = dummyNode;
while (tempHead.next.val <= pre.val) {
tempHead = tempHead.next;
}
//此时我们已经找到了合适位置，我们需要进行插入，大家可以画一画
last.next = pre.next;
pre.next = tempHead.next;
tempHead.next = pre;
//继续往下移动
pre = last.next;
}
return dummyNode.next;
};
Python Code:
class Solution:
def insertionSortList(self, head: ListNode) -> ListNode:
if head is None or head.next is None:
return head
# 哑节点
dummyNode = ListNode(-1, head)
# pre负责指向新元素，last 负责指向新元素的前一元素
# 判断是否需要执行插入操作
pre = head.next
last = head
while pre is not None:
# 不需要插入到合适位置，则继续往下移动
if last.val <= pre.val:
pre = pre.next
last = last.next
continue
# 开始出发，查找新元素的合适位置
temphead = dummyNode
while temphead.next.val <= pre.val:
temphead = temphead.next
# 此时我们已经找到了合适位置，我们需要进行插入，大家可以画一画
last.next = pre.next
pre.next = temphead.next
temphead.next = pre
# 继续往下移动
pre = last.next
return dummyNode.next
Swift Code：
class Solution {
func insertionSortList(_ head: ListNode?) -> ListNode? {
if head == nil && head?.next == nil {
return head
}
//哑节点
var dummyNode = ListNode(-1)
dummyNode.next = head
//pre负责指向新元素，last 负责指向新元素的前一元素
//判断是否需要执行插入操作
var pre = head?.next
var last = head
while pre != nil {
//不需要插入到合适位置，则继续往下移动
if last!.val <= pre!.val {
pre = pre?.next
last = last?.next
continue
}
//开始出发，查找新元素的合适位置
var temphead = dummyNode
while temphead.next!.val <= pre!.val {
temphead = temphead.next!
}
//此时我们已经找到了合适位置，我们需要进行插入，大家可以画一画
last?.next = pre?.next
pre?.next = temphead.next
temphead.next = pre
//继续往下移动
pre = last?.next
}
return dummyNode.next
}
}
Go Code:
func insertionSortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil { return head }
root := &ListNode{
Next: head,
}
cur, nxt := head, head.Next
for nxt != nil {
// 有序的不需要换位置
if cur.Val <= nxt.Val {
cur = cur.Next
nxt = nxt.Next
continue
}
temp := root
for temp.Next.Val <= nxt.Val {
temp = temp.Next
}
// 此时找到合适的位置
cur.Next = nxt.Next
nxt.Next = temp.Next
temp.Next = nxt
// 继续向下
nxt = cur.Next
}
return root.Next
}
