重庆建设工程查询网站,专业微信网站,做一个网址需要多少钱,中国建设部监理工程师查询网站 #x1f4dd;个人主页#xff1a;Sherry的成长之路 #x1f3e0;学习社区#xff1a;Sherry的成长之路#xff08;个人社区#xff09; #x1f4d6;专栏链接#xff1a;数据结构 #x1f3af;长路漫漫浩浩#xff0c;万事皆有期待 文章目录链表OJ题(五)1. 合并… 个人主页Sherry的成长之路 学习社区Sherry的成长之路个人社区 专栏链接数据结构 长路漫漫浩浩万事皆有期待 文章目录链表OJ题(五)1. 合并两个有序链表1.1 思路--带哨兵位的头结点1.2 思路--不强行加头结点2.总结上一篇链表OJ题链接【链表OJ题(四)】反转链表
链表OJ题(五)
1. 合并两个有序链表
链接21. 合并两个有序链表
描述 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 示例1 输入l1 [1,2,4], l2 [1,3,4] 输出[1,1,2,3,4,4] 示例2 输入l1 [], l2 [] 输出[] 示例3 输入l1 [], l2 [0] 输出[0] 提示 两个链表的节点数目范围是 [0, 50] -100 Node.val 100 l1 和 l2 均按 非递减顺序 排列
1.1 思路–带哨兵位的头结点
之前做过一道题目叫做合并两个有序数组。其中有一种方法是创建一个新数组然后遍历两个数组将两个数组的较小的元素放置到新数组中。一个数组遍历完将没有放置的元素放置到新数组中然后拷贝回原数组。
那么这道题能否借鉴它的思路 合并两个有序链表链表和数组不同数组形式的一种方法需要我们创建一个新数组。但是对于链表而言我们可以通过指针改变链接关系所以不需要创建新链表只需要修改即可。 有序数组的做法是将较小元素逐个尾插到新数组中那么我们也可以将较小元素尾插到链表中。
那么链表为空如何处理 这时就又要用到哨兵位(头结点)了我们给一个哨兵位 head它也不存储数据那么不就可以了但是注意有效数据从 head-next 开始。
但是尾插存在两个问题当尾插的时候我们需要找链表的尾而且当链表为空时需要特殊处理。为了避免每次找链表的尾那么我们就给定一个 tail这样只要将 tail 迭代就可以。
注意哨兵位需要释放否则会造成内存泄漏。
代码
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* head NULL, *tail NULL;if (list1 NULL){return list2;} if (list2 NULL){return list1;}// 哨兵位// 这里 tail 也需要动态开辟一下// 因为不在迭代时进行第一次插入的处理// tail 一开始为空指针会报错head tail (struct ListNode*)malloc(sizeof(struct ListNode)); while (list1 list2){if (list1-val list2-val){tail-next list1; // 当前结点链表的尾链接到 list1tail list1; // 链表的尾变成 list1list1 list1-next; // list1 并没有改变list1 迭代到list1的下一个节点}else{tail-next list2;tail list2;list2 list2-next;}}// 未放置完的元素// 这里和数组的完全不一样// 链表是串联的所以只需要把当前节点给到tail-next// 就可以全部串联if (list1){tail-next list1;}if (list2){tail-next list2;}// 释放哨兵位struct ListNode* ans head-next;free(head); return ans;
}1.2 思路–不强行加头结点
这道题目不使用哨兵位也能写但是使用这种方法时需要处理一下链表第一次合并时尾插的情况大体思路和带哨兵位差不多但需要注意一下细节
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{if (list1 NULL)return list2;if (list2 NULL)return list1;struct ListNode *head, *tail;head tail NULL;while (list1 list2){if (list1-val list2-val){// 第一次合并if (tail NULL){head tail list1;}else{tail-next list1;tail tail-next;}list1 list1-next;}else{// 第一次合并if (tail NULL){head tail list2;}else{tail-next list2;tail tail-next;}list2 list2-next;}}if (list1)tail-next list1;if (list2)tail-next list2;return head;
}2.总结
今天我们通过两种思路分析并完成合并两个有序链表这道链表OJ题目也更加深层次了解和使用了带哨兵位的头结点这个思路在之后的题目中将再次出现它的使用。希望我的文章和讲解能对大家的学习提供一些帮助。 当然本文仍有许多不足之处欢迎各位小伙伴们随时私信交流、批评指正我们下期见~
