目录
1. 题目描述及链接
题目链接：21. 合并两个有序链表 - 力扣（LeetCode）
题目描述：
将两个升序链表合并为一个新的 升序 链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
2. 解题思路
总思路：
创建一个新的链表。定义两个结构体指针变量，分别指向两个链表待比较结点，遍历原链表，依次对比选出值更小的结点依次尾插到新链表。
具体实现思路：
（1）由于需要依次对比两链表结点的大小值，故创建两个指针变量l1与l2分别用于指向链表1和链表2的当前比较的结点。
（2）由于需要将较小值结点尾插到新链表，故需创建指针变量newTail指向当前新链表的尾结点，每次插入一个结点就更新一次newTail。
且需返回新链表的头结点，故需创建指针变量newTail指向新链表的尾结点。
（3）直至对链表1或链表2完成遍历，即l1或l2为空，则此时将不为空的链表后续的若干结点直接拼接到新链表的newTail之后即可。
（4）考虑特殊情况：链表1为空或链表2为空时，根据当前代码逻辑，l1或l2其中一个为NULL，则newTail为空，若执行newTail->next会导致对空指针的解引用，故需单独讨论处理。
处理逻辑为：若链表1为空，则直接返回链表2的头结点；
若链表2为空，则直接返回链表1的头结点；
3. 程序
3.1 第一版
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
// 判空
if(list1==NULL){
return list2;
}
if(list2==NULL){
return list1;
}
ListNode* l1=list1;
ListNode* l2=list2;
// 新链表
ListNode* newHead=NULL;
ListNode* newTail=NULL;
while(l1 && l2){
if(l1->val<l2->val){
// 尾插l1
if(newHead==NULL){
newHead=newTail=l1;
}else{
newTail->next=l1;
newTail=newTail->next;
}
l1=l1->next;
}else{
// 尾插l2
if(newHead==NULL){
newHead=newTail=l2;
}else{
newTail->next=l2;
newTail=newTail->next;
}
l2=l2->next;
}
}
// l1或l2为空
if(l2){
newTail->next=l2;
}
if(l1){
newTail->next=l1;
}
return newHead;
}3.2 第二版
在上文程序中的while循环体内，易观察到while循环体内的代码重复：
优化思路如下：
此处重复原因：新链表存在空和非空两种情况，故而可令newHead和newTail初始状况不为空：
初始化时为newHead何newTail动态申请一个结点的空间，但不存储有效数据。
同时最终返回值也不再是newHead，而是newHead->next；
解题程序如下：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
// 判空
if(list1==NULL){
return list2;
}
if(list2==NULL){
return list1;
}
ListNode* l1=list1;
ListNode* l2=list2;
// 新链表
ListNode* newHead,*newTail;
newHead=newTail=(ListNode*)malloc(sizeof(ListNode));
while(l1 && l2){
if(l1->val<l2->val){
// 尾插l1
newTail->next=l1;
newTail=newTail->next;
l1=l1->next;
}else{
// 尾插l2
newTail->next=l2;
newTail=newTail->next;
l2=l2->next;
}
}
// l1或l2为空
if(l2){
newTail->next=l2;
}
if(l1){
newTail->next=l1;
}
// 动态申请的空间手动释放
ListNode* ret=newHead->next;
free(newHead);
newHead=NULL;
return ret;
}