5
[ 链表OJ题--C语言 ] 合并两个有序链表
source link: https://blog.51cto.com/xingyuli/5282660
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[ 链表OJ题--C语言 ] 合并两个有序链表
原创目录
题目来源：
代码实现：
分析过程：
题目来源：
LeetCode第21题. 合并两个有序链表
题目描述：
![[ 链表OJ题--C语言 ] 合并两个有序链表_C语言](https://s8.51cto.com/images/202205/943193962afe47588d5696ba6c4e5e66b44d35.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=,x-oss-process=image/resize,m_fixed,w_1184)
![[ 链表OJ题--C语言 ] 合并两个有序链表_C语言_02](https://s8.51cto.com/images/202205/e366f8a63fc5e4484f43564783ab74606668dd.gif)
代码实现：
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;
}
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;
}
![[ 链表OJ题--C语言 ] 合并两个有序链表_链表_03](https://s9.51cto.com/images/202205/14475b912e7346dcc224128c177a55380db5f6.gif)
分析过程：
![[ 链表OJ题--C语言 ] 合并两个有序链表_链表_04](https://s9.51cto.com/images/202205/b8f004f63c7702c73155347843464ed84cc916.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=,x-oss-process=image/resize,m_fixed,w_1184)
![[ 链表OJ题--C语言 ] 合并两个有序链表_C语言_05](https://s4.51cto.com/images/202205/47eca0c30be8ad8d840878e2c634b43dd4c6bf.gif)
在本题中，我们需要创建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;
if(list2==NULL) return list1;
![[ 链表OJ题--C语言 ] 合并两个有序链表_数据结构_06](https://s4.51cto.com/images/202205/620ac8956545affebee782b8f14278cd459b5a.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=,x-oss-process=image/resize,m_fixed,w_1184)
![[ 链表OJ题--C语言 ] 合并两个有序链表_数据结构_07](https://s7.51cto.com/images/202205/b8243d586095378802a3993ac120c54be89cd8.png?x-oss-process=image/watermark,size_14,text_QDUxQ1RP5Y2a5a6i,color_FFFFFF,t_100,g_se,x_10,y_10,shadow_20,type_ZmFuZ3poZW5naGVpdGk=,x-oss-process=image/resize,m_fixed,w_1184)
![[ 链表OJ题--C语言 ] 合并两个有序链表_C语言_08](https://s6.51cto.com/images/202205/29b527c38daea6b21278376f1ec0d2f2cbf7e3.gif)
(本题完)
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK