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

110 阅读 0 评论 73 点赞

我是靠谱客的博主忧心皮皮虾，这篇文章主要介绍（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：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
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：

递归

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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;
    }
};