（LeetCode C++）合并两个有序链表

57 阅读 0 评论 38 点赞

我是靠谱客的博主忧心皮皮虾，最近开发中收集的这篇文章主要介绍（LeetCode C++）合并两个有序链表，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

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

示例 1：

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

输入：l1 = [], l2 = []
输出：[]
示例 3：

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

提示：

两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按非递减顺序排列

链表：

Code：

class ListNode
{
public:
    int val;
    ListNode *next;

    // Function overload
    ListNode()
    {
        this->val=0;
        this->next=nullptr;
    }

    ListNode(int x)
    {
        this->val=x;
        this->next=nullptr;
    }

    ListNode(int x,ListNode *y)
    {
        this->val=x;
        this->next=y;
    }

};

Code 1：

循环+双指针

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1,ListNode *list2)
    {
        // 如果list1为空，无需合并，结果直接是list2
        if(list1==nullptr)
        {
            return list2;
        }
        // 如果list2为空，无需合并，结果直接是list1
        if (list2==nullptr)
        {
            return list1;
        }

        // 创建一个结果链表，保存合并的结果
        ListNode *resultNode=new ListNode();
        ListNode *p=resultNode;

        // 循环
        while(list1!=nullptr&&list2!=nullptr)
        {
            // 若list1的表头小于list2的表头
            if(list1->val<list2->val)
            {
                // 结果链表的表头指针指向list1的表头
                p->next=list1;
                // list1的表头指针后移
                list1=list1->next;
            }
            else
            // 若list2的表头小于list1的表头
            {
                // 结果链表的表头指针指向list2的表头
                p->next=list2;
                // list2的表头指针后移
                list2=list2->next;
            }
            // 结果链表的表头指针后移
            p=p->next;
        }
        // 如果list1为空
        if(list1==nullptr)
        {
            // 则将list2接到结果链表之后
            p->next=list2;
        }
        // 如果list2为空
        else if(list2==nullptr)
        {
            // 则将list1接到结果链表之后
            p->next=list1;
        }

        // 与正确结果相比，resultNode多了一个表头
        // 需要去掉表头
        resultNode=resultNode->next;
        // 输出合并结果
        return resultNode;
    }
};

Code 2：

递归

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1,ListNode *list2)
    {
        // 如果list1为空，无需合并，结果直接是list2
        if(list1==nullptr)
        {
            return list2;
        }
        // 如果list2为空，无需合并，结果直接是list1
        if (list2==nullptr)
        {
            return list1;
        }
        
        // 递归
        if(list1->val<list2->val)
        {
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }
        list2->next=mergeTwoLists(list1,list2->next);
        return list2;
    }
};

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-two-sorted-lists