LeetCode每日一题Day5——21. 合并两个有序链表

命运之光

发布于 2024-03-20 12:55:33

2440

文章被收录于专栏：我在本科期间写的文章我在本科期间写的文章

21. 合并两个有序链表

正确答案

方法一：暴力破解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy=ListNode(-1);
        ListNode *prev=&dummy;
        while(l1 != nullptr && l2 != nullptr){
            if(l1->val < l2->val){
                prev->next=l1;
                l1 = l1->next;
            }
            else{
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }
        prev->next=l1==nullptr?l2:l1;
        return dummy.next;
    }
};

提交记录

详细解析该题代码（方法一：暴力破解）

这段代码是一个用于合并两个升序链表的C++函数，其中使用了单链表的数据结构。现在，我将逐行解析代码的功能：

定义了一个单链表的数据结构 ListNode，每个节点包含一个整数值 val 和一个指向下一个节点的指针 next。该数据结构提供了三个构造函数：

- ListNode()：无参构造函数，初始化 val 为0，next 为nullptr。
- ListNode(int x)：带参构造函数，初始化 val 为给定的整数x，next 为nullptr。
- ListNode(int x, ListNode *next)：带参构造函数，初始化 val 为给定的整数x，next 为指向给定节点的指针。

接下来是一个C++类 Solution 的定义。该类中有一个公共成员函数 mergeTwoLists，它用于合并两个升序链表。该函数接受两个指向链表头节点的指针 l1 和 l2，并返回一个指向合并后链表头节点的指针。
在 mergeTwoLists 函数中：

- 创建了一个名为 dummy 的 ListNode 对象，并初始化其值为-1。这个 dummy 节点在合并过程中起到了哨兵节点的作用，它不包含实际数据，只是用来简化代码逻辑。
- 创建一个指向 dummy 节点的指针 prev，用于跟踪合并后链表的末尾节点。

使用 while 循环进行链表的合并，循环条件是 l1 和 l2 都不为nullptr（即还有节点需要合并）。

- 在循环体中，比较 l1->val 和 l2->val 的大小，如果 l1 的值小于 l2，则将 l1 添加到合并后链表的末尾，并将 l1 指针移动到下一个节点；否则，将 l2 添加到合并后链表的末尾，并将 l2 指针移动到下一个节点。
- 然后，将 prev 指针移动到合并后链表的末尾。

当循环结束后，有可能 l1 或 l2 中还有剩余节点未合并，此时需要将剩余的部分直接添加到合并后链表的末尾。这里使用了三目运算符 l1==nullptr?l2:l1 来确定应该将哪个链表的剩余部分添加到末尾。
最后，返回 dummy.next，即合并后链表的头节点的指针。由于 dummy 是一个临时节点，实际的合并后链表从 dummy.next 开始。

总体来说，这段代码通过迭代遍历两个升序链表，根据节点值的大小将节点逐个合并，并返回合并后的链表头节点的指针。合并后的链表仍然保持升序。

方法二：递归法解题

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        }
        if (l2 == nullptr) {
            return l1;
        }
        
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

提交记录

详细解析该题代码（方法二：递归法解题）

除了迭代法外，还有递归法可以解决合并两个升序链表的问题。我将为你介绍递归法的解题思路和代码示例。

递归法的思路是基于合并两个升序链表的子问题。假设我们已经知道如何合并两个以 l1 和 l2 为头节点的升序链表，我们可以将问题转化为合并以 l1->next 和 l2 为头节点的升序链表，并将结果连接到 l1 上。这样，问题规模不断缩小，最终合并两个链表的问题将转化为合并两个小一些的链表的问题，直到其中一个链表为空。

下面是用递归法解决问题的代码示例：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        }
        if (l2 == nullptr) {
            return l1;
        }
        
        if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

在递归函数 mergeTwoLists 中，我们首先处理边界情况，即如果其中一个链表为空，直接返回另一个链表。然后，我们比较 l1->val 和 l2->val 的大小，如果 l1 的值小于 l2，则将 l1 的下一个节点与合并后的链表连接，并返回 l1；否则，将 l2 的下一个节点与合并后的链表连接，并返回 l2。

递归法的思路较为简洁，但需要注意对递归深度的控制，防止出现栈溢出的情况。在实际应用中，可能需要对递归深度进行限制或使用迭代法来处理大规模的链表。