合并顺序链表（C++）

刷题平台

牛客网

题目描述

输入连个单调递增的链表，输出两个链表合成后的链表，并保证新的链表是非单调递减的。

解题思路

• 当链表 1 为空，则直接返回链表 2 ；当链表 2 为空时，直接返回链表 1；当链表 1链表 2都为空时，返回空。
• 判断两个链表的头结点的大小，将较小的结点放入新链表。然后通过递归的方法，遍历两个链表。

代码

struct ListNode
{
    int val;
    struct ListNode *next;
    ListNode(int x): val(x), next(NULL) {}
};

class Solution
{
public:
    ListNode *Merge(ListNode *pHead1, ListNode *pHead2)
    {
        if (pHead1 == NULL)
            return pHead2;
        else if (pHead2 == NULL)
            return pHead1;
        ListNode *NewMerge = NULL; // 新链表
        if (pHead1->val < pHead2->val) // 判断两链表的头结点的大小
        {
            NewMerge = pHead1;
            NewMerge->next = Merge(NewMerge->next, pHead2);
        }
        else
        {
            NewMerge = pHead2;
            NewMerge->next = Merge(pHead1, NewMerge->next);
        }
        return NewMerge;
    }
};

---

参考博文链接：https://cuijiahua.com/blog/2017/12/basis_16.html