Leetcode刷题营第十九题：对链表进行插入排序

147. 对链表进行插入排序

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

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

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

示例 1：

输入: head = [4,2,1,3]
输出: [1,2,3,4]

示例 2：

输入: head = [-1,5,3,4,0]
输出: [-1,0,3,4,5]

提示：

• 列表中的节点数在 [1, 5000]范围内
• -5000 <= Node.val <= 5000

思路：遍历链表，每次拿下一个节点，新拿下的节点跟之前拿下的节点进行比较，再进行链表的插入。

代码实现：

struct ListNode* insertionSortList(struct ListNode* head) {if(head == NULL || head->next == NULL){return head;}struct ListNode* Cur = head->next;struct ListNode* new_head = head;new_head->next = NULL;while (Cur){   struct ListNode* new_Cur = new_head;struct ListNode* Next = Cur->next;if(Cur->val < new_Cur->val){Cur->next = new_Cur;new_head = Cur;}else{struct ListNode* prev = new_Cur;new_Cur =new_Cur->next;while (new_Cur && Cur->val >= new_Cur->val){prev = new_Cur;new_Cur =new_Cur->next;}prev->next = Cur; Cur->next = new_Cur;}Cur = Next;}return new_head;
}

这里同样我们可以使用到哑指针进行优化！

struct ListNode* insertionSortList(struct ListNode* head) {if (head == NULL || head->next == NULL)return head;struct ListNode dummy;dummy.next = NULL;  // dummy 作为新排序链表头部struct ListNode* cur = head;while (cur) {struct ListNode* next = cur->next;// 在 dummy 链中找插入位置struct ListNode* prev = &dummy;while (prev->next && prev->next->val < cur->val) {prev = prev->next;}// 插入 cur 节点到 prev->next 前面cur->next = prev->next;prev->next = cur;cur = next; // 处理下一节点}return dummy.next;
}

这里对链表的插入需要注意前后节点的指向，需要改变前后节点所指向的位置！

本期就到这结束了，谢谢大家的点赞收藏！！！