Ieetcode——21.合并两个有序链表

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

 完！