⭐️ 题目描述
🌟 leetcode链接:对链表进行插入排序
思路与图解:
遍历链表,当前结点依次与前面的结点比较,选择插入位置。每次与前面的结点比较需要从头开始比较,所以定义一个 tempHead
指针,在定义一个 tempHeadPrev
指针记录 tempHead
前一个结点位置(方便插入),在定义一个 tail
记录前面区间的尾结点,当插入时需要考虑头插还是中间插入,当当前元素比前面区间元素都大时,说明无需插入当前位置合适,只需要改变 tail
指针(相当于确定新区间),下次继续迭代即可。文章来源:https://www.toymoban.com/news/detail-546574.html
1️⃣ 代码:
文章来源地址https://www.toymoban.com/news/detail-546574.html
struct ListNode* insertionSortList(struct ListNode* head){
// 从第二个结点开始遍历链表
struct ListNode* cur = head->next;
// 记录前面区间的尾部
struct ListNode* tail = head;
while (cur) {
// 记录下遍历的下一个位置
struct ListNode* next = cur->next;
// 区间的头部
struct ListNode* tempHead = head;
// 区间头部的前一个结点
struct ListNode* tempHeadPrev = NULL;
// cur 依次和区间元素进行比较确认插入位置
while (cur != tempHead && cur->val > tempHead->val) {
tempHeadPrev = tempHead;
tempHead = tempHead->next;
}
// 如果 cur 比 当前区间所有结点数据都大 更新尾区间
if (cur == tempHead) {
tail = cur;
}
else {
// 插入
if (tempHeadPrev == NULL) {
// 头插入更新头指针
head = cur;
} else {
// 中间插入
tempHeadPrev->next = cur;
}
tail->next = cur->next;
cur->next = tempHead;
}
// 迭代
cur = next;
}
return head;
}
到了这里,关于leetcode 147.对链表进行插入排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!