朋友们、伙计们，我们又见面了，今天给大家带来的是LeetCode中21题：合并两个有序链表
数 据 结 构：数据结构专栏
作 者：stackY、
C 语 言 ：C语言专栏
LeetCode ：LeetCode刷题训练营
LeetCode--21.合并两个有序链表 ：https://leetcode.cn/problems/merge-two-sorted-lists/description/
目录
1.题目介绍
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
编辑
2.实例演示
编辑
3.解题思路
合并两个有序链表我们通常采用的方法是遍历两个链表，然后取较小的结点进行尾插，尾插法和我们之前见到过的OJ题：删除链表元素中使用的方法很相似，当然这里也是要区分第一次尾插和接下来的尾插，如果有一个链表为空那么直接返回另外一个链表的头结点，如果两个链表都不为空，这时如果一个结点尾插完了，另外一个结点还没有结束，这时就不需要在依次尾插，直接将剩下的结点链接在后面即可：
编辑
代码演示：
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){ struct ListNode* phead1 = list1; struct ListNode* phead2 = list2; //新的头和新的尾 struct ListNode* newhead = NULL; struct ListNode* tail = NULL; //有一个链表为空则返回其它链表的头 if(phead1 == NULL) { return phead2; } if(phead2 == NULL) { return phead1; } //正常情况 while(phead1 && phead2) { //小的进行尾插 if(phead1->val > phead2->val) { //第一次尾插 if(tail == NULL) { newhead = tail = phead2; } else { //尾插 tail->next = phead2; //更新尾 tail = tail->next; } //迭代 phead2 = phead2->next; } else { if(tail == NULL) { newhead = tail = phead1; } else { tail->next = phead1; tail = tail->next; } phead1 = phead1->next; } } //一个链表尾插完之后将剩下的直接链接在尾的后面 if(phead1 == NULL) { tail->next = phead2; } if(phead2 == NULL) { tail->next = phead1; } return newhead; }
今天的博客就分享到这里，喜欢的老铁留下你的三连，感谢感谢！我们下期再见！！
