【数据结构OJ题】合并两个有序链表

原题链接：https://leetcode.cn/problems/merge-two-sorted-lists/description/

目录

1. 题目描述

2. 思路分析

3. 代码实现

---

1. 题目描述

2. 思路分析

可以先创建一个空链表，然后依次从两个有序链表中选取最小的进行尾插操作。（有点类似双指针的操作~）

我们可以用不带哨兵位和带哨兵位两种方法实现：

不带哨兵位：

如果两个链表有一个为空，直接返回另一个链表即可。

如果两个链表都是非空的，我们就创建一个结构体指针head和一个结构体指针tail，都初始化为空指针NULL，之后分别用来指向新链表的头和尾。

同时遍历两个链表，当有一个链表遍历完时停止。这里使用while(list1&&list2)进行循环。

当空链表插入第一个结点（也就是tail==NULL）时需要单独考虑，让头指针head和尾指针next都指向此时值较小的那个结点即可。

其他情况，正常尾插即可，就是让tail->next指向值较小的结点。之后让tail指向当前插入的结点（也就是让tail往后走一步），然后让相对应的list1或者list2往后走一步即可。

因为有可能while循环结束时，还有链表的结点没有被插入到新链表。所以我们要用if语句判断，将剩余的结点直接插入到新链表。

最后我们返回头指针head即可。

带哨兵位：

带哨兵位最大的好处是方便尾插，不用单独考虑在新链表插入第一个结点时的情况了，因为带哨兵位让每一个结点地位都一样了。

这里相比不带哨兵位多的一些操作就是要先用malloc()函数申请一个结点作为哨兵位，让head和tail一开始都直接指向这个结点。

当完成合并操作后，让头指针head往后走一步，指向哨兵位后面一个结点。

然后使用free()释放掉哨兵位。

最后返回head即可。

3. 代码实现

不带哨兵位：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
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=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;
}

带哨兵位：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
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;//带一个哨兵位，方便尾插head=tail=(struct ListNode*)malloc(sizeof(struct  ListNode));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);return head;
}