朋友们、伙计们，我们又见面了，今天给大家带来的是LeetCode中21题：合并两个有序链表

数 据 结 构：数据结构专栏
作          者：stackY、

C  语   言  ：C语言专栏

LeetCode ：LeetCode刷题训练营

LeetCode--21.合并两个有序链表 ：https://leetcode.cn/problems/merge-two-sorted-lists/description/

目录

1.题目介绍

2.实例演示 

 3.解题思路

---

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;
}

今天的博客就分享到这里，喜欢的老铁留下你的三连，感谢感谢！我们下期再见！！