【leetcode天梯】链表 · 021 合并两个有序链表

题目描述：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：

输入：l1 = [], l2 = []
输出：[]

示例 3：

输入：l1 = [], l2 = [0]
输出：[0]

题目链接：

21. 合并两个有序链表 - 力扣（LeetCode）https://leetcode.cn/problems/merge-two-sorted-lists/

---

解题思路：

常规法1：建立一个新链表接收 

这种方法我觉得应该是最最最基本的做法了，使用四个指针来进行操作，其中两个指针用来遍历原链表，一个指针用来标识新链表的表头，另一个指针用来标识新链表的表尾，方便新结点的尾插。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode*n1=list1; //n1指针用来遍历list1
    struct ListNode*n2=list2; //n2指针用来遍历list2
    struct ListNode*newHead=NULL; 
    struct ListNode*tail=NULL;
    while(n1&&n2) //当n1或n2有一个为NULL时就跳出循环
    {
        if(n1->val<=n2->val) //当n1指向的结点的值小于等于n2后
        {
            if(newHead==NULL) //当新链表为空时
            {
                newHead=n1; //将n1作为新链表的头结点
                tail=n1;
                n1=n1->next;
            }
            else //当新链表不为空
            {
                tail->next=n1; //将新链表的尾结点连接到n1
                tail=n1;
                n1=n1->next;
            } 
        }
        else //当n1指向的结点值大于n2时
        {
            if(newHead==NULL) //当新链表为空时
            {
                newHead=n2; //将n2作为新链表的头结点
                tail=n2;
                n2=n2->next;
            }
            else //当新链表不为空
            {
                tail->next=n2; //将新链表的尾结点连接到n1
                tail=n2;
                n2=n2->next;
            }    
        }
    }
    if(newHead==NULL) //说明有一个链表一开始就是空
    {
        if(n1==NULL)
            return n2;
        else if(n2==NULL)
            return n1;
        else if(n1==NULL&&n2==NULL)
            return NULL;
    }
    if(n1==NULL)
        tail->next=n2;
    if(n2==NULL)
        tail->next=n1;
    return newHead; 
}

总结一下：我们发现这道题之所以写的略长，是因为需要讨论新链表头指针可能为空或不为空的情况发生，对于新链表的头结点可能为空的问题，想必我们在【移除链表元素】这一话中就已经介绍了，使用哨兵法可以大大简化上述代码。

常规法2：哨兵法

为了简化上述操作，除了建立一个哨兵位以外，其实我们只需要设置两个指针就好了，n1和n2指针完全可以用原本的list1和list2来替代，因为这道题的结果我们不需要返回原链表，只需要返回一个合并后的新链表即可。

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode* newHead=NULL,*tail=NULL;
    newHead=tail=(struct ListNode*)malloc(sizeof(struct ListNode));//起初tail和newHead指向同一个动态结点空间
    while(list1&&list2) //当list1或list2有一个为空跳出循环
    {
        if(list1->val<=list2->val)
        {
            if(tail==NULL) //当新链表为空时
            {
                newHead->next=tail=list1; //将list1指向的结点链接在哨兵位之后
            }
            else //当新链表不为空时
            {
                tail->next=list1; //将list1指向的结点直接链接在新链表之后
                tail=list1;
            }
            list1=list1->next; //list1向后走一步
        }
        else
        {
            if(tail==NULL)
            {
                newHead->next=tail=list2;
            }
            else
            {
                tail->next=list2;
                tail=list2;
            }
            list2=list2->next;
        }    
    }
    if(list1==NULL)
        tail->next=list2;
    if(list2==NULL)
        tail->next=list1;
    struct ListNode* list=newHead->next; //定义一个list指针指向哨兵位结点之后
    free(newHead); //free掉哨兵位结点
    return list;
}

总结一下：这里使用哨兵法的巧妙之处就在于起初将tail和newHead都指向同一个哨兵位结点空间。比如当有一个list为空时，此时无法进入while循环，但是却可以和进入while循环后跳出的程序共用同一段代码，而不需要分类讨论，这就是因为起初tail和newHead指向的是同一个哨兵位结点空间，因此对于那些没有进入循环的程序来说，它们执行的tail->next=list1，就相当于执行了newHead->next=list1。最终它们和那些进入while循环的程序一样，最后共用一个return newHead->next语句就都能实现输出操作了。