追风赶月莫停留,平芜尽处是春山。这篇文章主要讲述[ 链表OJ题--C语言 ] 合并两个有序链表相关的知识,希望能为你提供帮助。
【[ 链表OJ题--C语言 ] 合并两个有序链表】
目录
题目来源:
代码实现:
分析过程:
题目来源:LeetCode第21题. 合并两个有序链表
题目描述:
代码实现:struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
if(list1==NULL) return list2;
if(list2==NULL) return list1;
struct ListNode* head = NULL,*tail = NULL;
while(list1 &
&
list2)
if(list1->
val <
list2->
val)
if(tail == NULL)
head = tail = list1;
else
tail->
next = list1;
tail = list1;
list1 = list1->
next;
else
if(tail == NULL)
head = tail = list2;
else
tail->
next = list2;
tail = list2;
list2 = list2->
next;
if(list1)
tail->
next = list1;
if(list2)
tail->
next = list2;
return head;
分析过程:
在本题中,我们需要创建2个新的结构体指针head和tail,分别用来表示合成后链表的头和尾,因此在合成前,我们要将head和tail置空。
过程:
1、比较list1->
val和list2->
val,如果list1小,这时list1的头结点,就将是新链表的头结点,合成链表中此时只有这一个元素,因此我们将head和tail都赋为list1,由于list1第一个节点比较完了,因此将list1走向下一个节点。list1=list1->
next。
2、当比较到第二个元素时,如果此时list2->
val小于list1->
val,这时tail的next就要指向list2,tail->
next = list2,list2也要继续走向list2的下一个元素,list2 = list2->
next,tail也要继续向下走,要一直保证tail的next是空,因为tail要一直将list1和list2中较小的值链接起来。
3、就这样持续循环下去,当其中的某一个list链表走向空,也就是list==NULL时,合成的链表的尾结点tail直接链接到另外一个list链表即可,因为list1和list2均为升序链表,并且每次新合成链表只链接一个结点,因此list两个链表一定有先链接完和后链接完之分。
4、特殊情况:当list1或者list2有某一链表为空时,返回另一个链表
if(list1==NULL) return list2;
if(list2==NULL) return list1;
(本题完)
推荐阅读
- XX公司反映4层楼上网卡慢
- mq从零开始实现 mq-07-负载均衡 load balance
- 通俗理解大数据及其应用价值
- springboot处理blog字段
- Intellij官方中文语言包,它来了
- [OpenCV实战]34 使用OpenCV进行图像修复
- 一次实战挖掘软件逻辑漏洞
- vim的简单使用
- 跨越时空的对白——async&await分析