选择网站建设公司好,可以做网站的魔盒,洛阳专业网站设计开发制作建站公司,制作板块的网站全文目录引言合并两个有序链表题目描述方法一#xff1a;将第二个链表合并到第一个思路实现方法二#xff1a;尾插到哨兵位的头节点思路实现总结引言
在前面两篇文章中#xff0c;我们介绍了几道链表的习题#xff1a;反转链表、链表的中间结点、链表的倒数第k个结点…
全文目录引言合并两个有序链表题目描述方法一将第二个链表合并到第一个思路实现方法二尾插到哨兵位的头节点思路实现总结引言
在前面两篇文章中我们介绍了几道链表的习题反转链表、链表的中间结点、链表的倒数第k个结点
戳我看反转链表详解哦 戳我看链表的中间结点与链表的倒数第k个结点详解哦
本篇文章中将继续介绍关于链表的题目合并两个有序链表 合并两个有序链表OJ链接
合并两个有序链表
题目描述 这道题要求我们将两个有序链表合并为一个链表并返回合并后链表的首结点地址。 参数为两个链表的首结点地址两个链表均为非递减排序即链表中的数据为递增或相等序列。结构体变量与主函数部分已经定义我们只需要实现接口即可。
在之前我们做过合并两个有序数组的题目我们可以使用双指针的方法将一数组中的元素按照顺序插入到另一数组中即从后向前遍历两个数组将较大的元素插入到数组的末尾。 对于链表的合并我们也可以借鉴这种方法
方法一将第二个链表合并到第一个
思路
我们可以创建用两个指针从前向后分别遍历两个链表 若list1中指针指向的结点的数据大于list2中指针指向的将list2中的元素插入到list1中元素的前面然后list1中的指针位置不变list2中的指针向后移动一个结点若list1中指针指向的结点小于list2中的list1中的指针向前移动一个结点。
若list1中的指针遍历到末尾则说明list2中还有结点没有插入到list2中且这些结点的数据大于list1中的所以直接将这个指针插入到list1末尾即可。
但是这样的方法会有些复杂尤其是在插入的时候的情况较麻烦这一点大家在后面的实现中可以体会到。
实现
为了使代码更简洁我们可以对结构体名称重命名
typedef struct ListNode ListNode;要实现这个算法我们首先需要两个指针变量cur1与cur2将它们分别初始化为两个链表的首结点地址
ListNode* cur1 list1;
ListNode* cur2 list2;并且当我们要将cur2指向的结点插入到cur1指向的结点前时需要一个指向cur1前面的结点的地址用来辅助我们将这个指针初始化为NULL
ListNode* beforecur1 NULL;首先我们需要判断链表2是否为空链表通过判断cur2的值即可当cur2的值为NULL时直接返回第一个链表的首结点地址list1
然后while循环循环需要cur1与cur2都不为空
在循环中判断cur1-val的与cur2-val的大小 若cur1-val大于cur2-val有两种情况 若cur1是链表的第一个结点即beforecur的值为NULL没有被改变我们就需要将cur2指向的结点头插到list1中。即先将list2赋值为cur2-next将其向后移动一个结点然后将cur2-next赋值为list1即原来第一个链表的首结点地址然后将beforecur1赋值为cur2即将其移动到cur1的前一个结点处最后将list1改为cur2即现链表1的首结点将cur2改为list2即cur2在链表2中向后移动一个结点。 若cur1不是链表的第一个结点我们就将cur2指向的结点插入到cur1指向结点的前面。即先将list2赋值为cur2-next将其向后移动一个结点然后将beforecur1-next改为cur2即让cur1前面的结点连接上cur2然后将beforecur1赋值为cur2即将其移动到cur1的前一个结点处然后将cur2-next改为cur1即让cur2连接上cur1.最后将cur2改为list2即cur2在链表2中向后移动一个结点。
若cur1-val小于等于cur2-val将cur1向后移动一个结点即可 首先将beforecur1改为cur1即向后移动一个结点。然后将cur1改为cur1-next即将cur1向后一动一个结点即可 typedef struct ListNode ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{ListNode* cur1 list1;ListNode* beforecur1 NULL;ListNode* cur2 list2;if (cur2 NULL){return list1;}while (cur1 cur2){if (cur1-val cur2-val){if (beforecur1 NULL){list2 cur2-next;cur2-next list1;beforecur1 cur2;list1 cur2;cur2 list2;}else{list2 cur2-next;beforecur1-next cur2;beforecur1 cur2;cur2-next cur1;cur2 list2;}}else{beforecur1 cur1;cur1 cur1-next;}}if (cur2){if (beforecur1 NULL){list1 cur2;}else{beforecur1-next cur2;}}return list1;
}方法二尾插到哨兵位的头节点
思路
我们可以直接创建一个哨兵位的头结点然后将cur1与cur2中的较大值尾插到该哨兵位的头节点后。这样就可以避免我们在cur1前插入结点时的复杂情况 不需要判断cur1是否为第一个结点并且尾插要比在前面插入更加方便。
实现
为实现这个算法在需要结构体指针cur1与cur2之外我们还需要两个指针用来表示新的链表的首结点地址与尾结点地址
ListNode* tail NULL;
ListNode* guard NULL;需要说明的是哨兵位的头节点是放在链表的起始位置可以使在链表中插入第一个结点时更方便。是不计入链表的数据的。 我们可以动态开辟这块空间
guard tail (ListNode*)malloc(sizeof(ListNode));当然需要if判断是否开辟成功
if (guard NULL){perror(malloc);}接下来可以直接进入循环需要cur1与cur2均不为空
在循环中判断cur1-val的与cur2-val的大小 若cur1-val大于cur2-val: 将tail-next改为cur2即将哨兵结点的末尾与cur2连接起来。然后将tail改为tail-next即使其依旧指向新链表的末尾。然后将cur2改为cur2-next即cur2向后移动一个结点。 若cur1-val小于等于cur2-val: 将tail-next改为cur1即将哨兵结点的末尾与cur1连接起来。然后将tail改为tail-next即使其依旧指向新链表的末尾。然后将cur1为cur1-next即cur1向后移动一个结点。
在结束循环后若cur2不为空说明链表2还剩余结点且大于其他的任何数据将其接在新链表的末尾即可 cur1不为空同理将其接到新节点末尾即可
最后需要注意的是guard指向的哨兵位的头节点是动态开辟的空间所以需要free释放。但是由于释放后就不能返回值所以先用一个ret指针记录guard-next的值等释放guard指向的空间后返回ret即可
typedef struct ListNode ListNode;struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{ListNode* cur1 list1;ListNode* cur2 list2;ListNode* tail NULL;ListNode* guard NULL;guard tail (ListNode*)malloc(sizeof(ListNode));if (guard NULL){perror(malloc);}while (cur1 cur2){if (cur1-val cur2-val){tail-next cur2;tail tail-next;cur2 cur2-next;}else{tail-next cur1;tail tail-next;cur1 cur1-next;}}if (cur2){tail-next cur2; }else{tail-next cur1;}ListNode* ret guard-next;free(guard);return ret;
}
总结
到此关于合并两个有序链表的两种解法已经介绍完了第二种方法显然是简单很多的。当然会有其他的算法解决欢迎大家在评论区讨论
后续可能还会有几道链表的相关题目欢迎大家持续关注哦
如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题欢迎大家在评论区提出
如果本文对你有帮助希望一键三连哦
希望与大家共同进步哦
