上海网站建设网站优化app,企业网站建设后期维护费用,上海比较好的设计院,银行网站建设方案视频LeetCode 147. 对链表进行插入排序 | C语言版LeetCode 147. 对链表进行插入排序题目描述解题思路思路一#xff1a;使用栈代码实现运行结果参考文章#xff1a;思路二#xff1a;减少遍历节点数代码实现运行结果参考文章#xff1a;[]()LeetCode 147. 对链表进行插入排序
…
LeetCode 147. 对链表进行插入排序 | C语言版LeetCode 147. 对链表进行插入排序题目描述解题思路思路一使用栈代码实现运行结果参考文章思路二减少遍历节点数代码实现运行结果参考文章[]()LeetCode 147. 对链表进行插入排序
题目描述
题目地址147. 对链表进行插入排序 给定单个链表的头 head 使用 插入排序 对链表进行排序并返回 排序后链表的头 。
插入排序 算法的步骤:
插入排序是迭代的每次只移动一个元素直到所有元素可以形成一个有序的输出列表。 每次迭代中插入排序只从输入数据中移除一个待排序的元素找到它在序列中适当的位置并将其插入。 重复直到所有输入数据插入完为止。 下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时从输入数据中删除一个元素(红色)并就地插入已排序的列表中。
对链表进行插入排序。 解题思路
思路一使用栈
代码实现
c
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/struct ListNode* insertionSortList(struct ListNode* head){if(headNULL) return head;//设置虚拟头结点struct ListNode* dummyHead(struct ListNode*)malloc(sizeof(struct ListNode));dummyHead-nextNULL;//dummyHead-nexthead;//当前节点要插入的节点curstruct ListNode* curhead;struct ListNode* predummyHead;//dummyHead-1(pre)-3-4-2(cur)-NULL(next)//如插入节点2操作如下while(cur!NULL){//循环中值不小于当前值时候就需要插入当前值了while(pre-next!NULL pre-next-valcur-val){prepre-next;}//在pre和next之间插入数据2struct ListNode* nextcur-next;//步骤一保存cur的下一个节点next因为本次循环结束后要把当前节点移动到下一个节点cur-nextpre-next;//步骤二cur2的指针域指向pre-next3pre-nextcur;//步骤三pre1的指针域指向cur2predummyHead;//步骤四pre重新指向虚拟头节点来找下一个插入位置curnext;//步骤五cur2节点直接往后移动到next//dummyHeadpre-1-2-3-4-NULL}return dummyHead-next;
}C
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* insertionSortList(ListNode* head) {if(headNULL) return head;//设置虚拟头结点ListNode* dummyHead new ListNode(0);//dummyHead-nexthead;//当前节点要插入的节点curListNode* curhead;ListNode* predummyHead;//dummyHead-1(pre)-3-4-2(cur)-NULL(next)//如插入节点2操作如下while(cur!NULL){//循环中值不小于当前值时候就需要插入当前值了while(pre-next!NULL pre-next-valcur-val){prepre-next;}//在pre和next之间插入数据2ListNode* nextcur-next;//步骤一保存cur的下一个节点next因为本次循环结束后要把当前节点移动到下一个节点cur-nextpre-next;//步骤二cur2的指针域指向pre-next3pre-nextcur;//步骤三pre1的指针域指向cur2predummyHead;//步骤四pre重新指向虚拟头节点来找下一个插入位置curnext;//步骤五cur2节点直接往后移动到next//dummyHeadpre-1-2-3-4-NULL}return dummyHead-next;}
};运行结果 参考文章
https://leetcode.cn/problems/insertion-sort-list/solutions/491331/147-kao-cha-lian-biao-zong-he-cao-zuo-xiang-jie-by/?q%E4%BB%A3%E7%A0%81orderBymost_relevant
思路二减少遍历节点数
代码实现
在这里插入代码片运行结果
参考文章
