C++解决合并两个排序的链表问题

问题描述

将两个已排序的链表合并成一个新的有序链表并返回。新链表是通过拼接两个链表并按升序排列得出的。

示例

示例1：

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

输出：[1,1,2,3,4,4]

示例2：

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

输出：[]

解决思路

本题思路比较简单，可以使用递归或循环的方法来实现链表合并，具体的思路分别如下：

递归实现

思路：

1. 递归结束条件：如果任一链表为空，说明合并完成，返回另一个链表。

2. 获取已排序的链表的头节点，假设链表1的头节点值小于等于链表2的头节点值，则链表1的头节点为合并后的链表头节点。

3. 对于当前合并好的链表的next，递归调用合并函数，传入排序后的两个链表头节点，再将返回的链表头节点设置为已排序好链表的next节点。

4. 最后返回已排序链表的头节点。

示例：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(!l1) return l2;
        if(!l2) return l1;
        if(l1->val <= l2->val){
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        }
        else{
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

循环实现

思路：

1. 新建一个哨兵节点，用来始终存储合并后链表的头节点。

2. 接着我们需要循环两个链表，比较当前链表的头节点值，找出较小值的节点放入合并链表的末尾。

3. 循环结束后，较短的链表就合并完了，剩余的节点直接接在合并后链表的尾部。

4. 返回哨兵节点的下一个节点，即合并后的链表的头节点。

示例：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy=new ListNode(-1);   //新建哨兵节点
        ListNode *head=dummy;

        while(l1 && l2){
            if(l1->val <= l2->val){
                head->next=l1;
                l1=l1->next;
            }
            else{
                head->next=l2;
                l2=l2->next;
            }
            head=head->next;
        }

        head->next=l1 ? l1 : l2;
        return dummy->next;
    }
};

总结

本题考察了链表的基本操作和常规思路，递归和循环两种方法本质上基本相同，但思路略有差异，需要我们根据实际情况而定。同时在链表的操作中需要注意一些边界，例如在链表的合并中需要新建一个哨兵节点等。