力扣---LeetCode21. 合并两个有序链表(链表经典题)

news/2024/4/24 21:00:55/文章来源:https://blog.csdn.net/ljq_up/article/details/130350799

文章目录

前言
21. 合并两个有序链表
- 链接：
- 方法一：取小尾插
- - 1.1代码：
  - 1.2 流程图：
  - 1.3 注意：
- 方法二：带哨兵位
- - 2.1代码：
  - 2.2流程图：
总结

前言

焦虑不会消除明天的悲伤只会让你今天的力量荡然无存
本章的内容是力扣每日随机一题的部分方法的解析

提示：以下是本篇文章正文内容，下面案例可供参考

21. 合并两个有序链表

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
在这里插入图片描述

链接：

21. 合并两个有序链表 link

方法一：取小尾插

1.1代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* head=NULL;struct ListNode* tail=NULL;if(list1==NULL)//判断是否是空链表return list2;if(list2==NULL)//判断是否是空链表return list1;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;
}

1.2 流程图：

在这里插入图片描述

1.3 注意：

要注意判断list1和;ist2是否是空链表
要考虑第一次插入的情况是没有结点的

方法二：带哨兵位

所谓带哨兵位的链表，就是一个附加的链表的节点，该节点作为第一个节点，它的值域并不存储任何东西，只是为了操作的方便引用的。
如果一个链表有哨兵节点的话,那么线性表的第一个元素应该是链表的第二个节点.

2.1代码：

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{struct ListNode* head=NULL;struct ListNode* tail=NULL;head=tail=(struct ListNode*)malloc(sizeof(struct ListNode));if(list1==NULL)return list2;if(list2==NULL)return list1;while(list1&&list2){if(list1->val<list2->val){tail->next=list1;tail=tail->next;list1=list1->next;}else{tail->next=list2;tail=tail->next;list2=list2->next;}}if(list1){tail->next=list1;}if(list2){tail->next=list2;}struct ListNode* del=head;head=head->next;free(del);del=NULL;return head;
}