21. 合并两个有序链表 - 力扣（LeetCode）

合并两个有序链表我们的思路是创建一个新链表，然后遍历已知的两个有序链表，并比较其节点的val值，将小的尾插到新链表中，然后继续遍历，直到将该两个链表的全部节点全部尾插到新链表中。下面我来画图分析一下如何进行遍历和尾插：

遍历和尾插的过程就如上图一般，接下来我们来实现代码。

我们在写代码的时候还应该注意一些特殊情况：有序链表为空的情况。 

我们看，对于这两种情况下：如果两个有序链表都为空，那么就返回NULL；如果只有一个为空，那就返回另外一个。 

分析到这里，我们就可以开始写代码了。(注意：该代码只包含解决该问题的函数部分，不包含主函数内容)

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{//有空链表if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}//无空链表//创建新链表，遍历两链表ListNode* newlist = NULL;ListNode* newtail = NULL;while(list1 && list2)//这两个链表只要有一个走到了NULL，就说明为NULL的链表已经全部尾插完了{if(list1->val <= list2->val){if(newlist == NULL){//新链表为空newlist = list1;newtail = list2;}else{//新链表不为空newtail->next = list1;newtail = newtail->next;}//尾插完后，遍历下一个节点list1 = list1->next;}else{if(newlist == NULL){//新链表为空newlist = list1;newtail = list2;}else{//新链表不为空newtail->next = list1;newtail = newtail->next;}//尾插完后遍历下一个节点list2 = list2->next;}}//跳出循环，说明有一个链表已经遍历完了，只需将另一个链表的剩余元素尾插到新链表if(list1 == NULL){//list1遍历完了，将list2尾插到新链表中newtail->next = list2;}else{//list2遍历完了，将list1尾插到新链表中newtail->next = list1;}return newlist;
}

我们写完之后，代码虽然可以成功解决问题，但是其中出现了很多重复的代码。 

哨兵位是一个有空间但是没有值的节点，而且是动态开辟的内存空间，所以我们现在就不能直接返回newist了，而是返回newlist->next，但是动态开辟的内存空间我们使用完之后就应该释放掉，所以我们应该先创建一个临时变量将newist->next存起来，然后将newlist释放掉，后返回临时变量。

所以我们要对该代码进行两部分的调整：

部分一：用来解决重复代码

部分二：用来解决动态内存开辟的释放以及哨兵位的引入对返回值的影响 

下面附上完整代码：

typedef struct ListNode ListNode;//避免因为类型名长而对其进行重命名
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) 
{//有空链表if(list1 == NULL){return list2;}if(list2 == NULL){return list1;}//无空链表//创建新链表，遍历两链表ListNode* newlist = (ListNode*)malloc(sizeof(ListNode));ListNode* newtail = newlist;while(list1 && list2)//这两个链表只要有一个走到了NULL，就说明为NULL的链表已经全部尾插完了{if(list1->val <= list2->val){newtail->next = list1;newtail = newtail->next;//尾插完后，遍历下一个节点list1 = list1->next;}else{newtail ->next = list2;newtail = newtail->next;//尾插完后遍历下一个节点list2 = list2->next;}}//跳出循环，说明有一个链表已经遍历完了，只需将另一个链表的剩余元素尾插到新链表if(list1 == NULL){//list1遍历完了，将list2尾插到新链表中newtail->next = list2;}else{//list2遍历完了，将list1尾插到新链表中newtail->next = list1;}ListNode* ret = newlist->next;free(newlist);newlist = NULL;return ret;
}

 完！