算法-合并两个排序的链表

一时失言乱红尘 2022-06-11 08:45 236阅读 0赞

**题目：**  
输入两个递增排序的链表，合并着两个链表并使新链表中的结点仍然是按照递增顺序的。例如输入的链表1和链表2如下，合并后的为链表3。链表的结点定义如下：

struct ListNode
    {
      int value;
      ListNode *next;
    };

![这里写图片描述][SouthEast]

**解题思路：**  
首先可以确定的是，链表1和链表2本身就是递增的，所以合并的过程可以从链表1，2的头结点开始，先比较1，2的头结点中值的大小，将小的值的结点（比如为链表1头结点）作为合并后的链表（链表3）的头结点。随后可以考虑成链表1的从原链表第二个结点开始，再次重复上面的步骤，这样就变成了一个递归问题。

![这里写图片描述][SouthEast 1]

![这里写图片描述][SouthEast 2]

![这里写图片描述][SouthEast 3]

**代码实现：**

ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1 == NULL)
            return pHead2;
        else if(pHead2 == NULL)
            return pHead1;
    
        ListNode* pMergedHead = NULL;
    
        if(pHead1->value < pHead2->value)
        {
            pMergedHead = pHead1;
            pMergedHead->next = Merge(pHead1->next, pHead2);
        }
        else
        {
            pMergedHead = pHead2;
            pMergedHead->next = Merge(pHead1, pHead2->next);
        }
    
        return pMergedHead;
    }

**测试例程：**

#include<iostream>
    using namespace std;
    
    struct ListNode
    {
    int value;
    ListNode *next;
    };
    void ShowList(ListNode* L);
    void CreateList(ListNode * L,int n,int initial);
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2);
    int main()
    {
        ListNode * L1 = new ListNode;
        L1->next = nullptr;
        ListNode * L2 = new ListNode;
        L2->next = nullptr;
        CreateList(L1,4,1);
        CreateList(L2,4,2);
        ShowList(L1);
        ShowList(L2);
        ListNode * L3 = Merge(L1,L2);
        ShowList(L3);
        getchar();
        return 0;
    }
    void CreateList(ListNode * L,int n,int initial)
    {
        L->value = initial;//输入第一个结点的数据值
        n--;
        for (int i = 0; i < n; i++)
        {   
            initial = initial+2;
            ListNode * p = new ListNode;
            p->value = initial;
            p->next = nullptr;
            L->next = p;
            L = p;
        }
    }
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(pHead1 == NULL)
            return pHead2;
        else if(pHead2 == NULL)
            return pHead1;
    
        ListNode* pMergedHead = NULL;
    
        if(pHead1->value < pHead2->value)
        {
            pMergedHead = pHead1;
            pMergedHead->next = Merge(pHead1->next, pHead2);
        }
        else
        {
            pMergedHead = pHead2;
            pMergedHead->next = Merge(pHead1, pHead2->next);
        }
    
        return pMergedHead;
    }
    void ShowList(ListNode* L)
    {
        ListNode *p =L;
        while (p)
        {
            cout<<p->value<<' ';
            p=p->next;
        }
        cout<<endl;
    }

结果如下：  
![这里写图片描述][SouthEast 4]

个人感觉值得注意的地方有下面几个：

（1）如果链表1，2为空，要考虑代码的鲁棒性。

（2）要考虑链表1，2中某结点的数值相等的情况，这个在else中包含了。  
![这里写图片描述][SouthEast 5]

（3）递归调用何时退出？  
递归退出的条件与为了防止空链表造成异常的判断是一个：

if(pHead1 == NULL)
            return pHead2;
        else if(pHead2 == NULL)
            return pHead1;

这就是这个代码很巧妙的地方，往往使一行代码两个甚至多个作用，我们举这样的例子：  
链表1 ： 1 3  
链表2 ： 2 4  
首先执行Merge(1,2)函数，进入if，  
进入第一次递归，执行Merge(3,2)，显然会进入else，  
进入第二次递归，执行Merge(3,4)，显然会进入if，  
进入第三次递归，执行Merge(NULL,4)，此时就进入了是否为空的判断，并返回4，同时递归结束。

（4）新的链表何时链接？  
我们可以这样理解这件事，还是上面的例子：  
链表1 ： 1 3  
链表2 ： 2 4  
代码会第一次进入后再递归三次，递归结束后要return四次（从里向外），每一次return时都会将链表向前链接一个结点，每一次return的结果其实是这样：  
1. 4  
2. 3 4  
3. 2 3 4  
4.1 2 3 4

[SouthEast]: /images/20220611/93cf505308f34edd96c71921bd26a7ad.png
[SouthEast 1]: /images/20220611/3e7d93633a784b78a01cc98710e308ac.png
[SouthEast 2]: /images/20220611/61813a40ba2447b3966735059f4b9581.png
[SouthEast 3]: /images/20220611/fa130431629842438b447f96f41b6d0b.png
[SouthEast 4]: /images/20220611/950f7e0f452e4c2687b44cba78349149.png
[SouthEast 5]: /images/20220611/9d29bc53e28f4b71a615cbc7a99745df.png