Leetcode21:合并两个有序链表

2021年3月9日 397点热度 0人点赞 0条评论

题目描述

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

示例

输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
输入:l1 = [], l2 = []
输出:[]
输入:l1 = [], l2 = [0]
输出:[0]

提示

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

解题思路

这道题的思路可以直接借鉴归并排序中两个有序数组的合并过程。这两个的区别仅仅在于:一个是连续空间,可以随机读取;另一个是非连续空间,不可随机读取。而且链表的头结点要特判处理。当然,与Leetcode25:K 个一组翻转链表类似,我们可以通过在头结点前添加结点hair来消除对头结点的特判处理。

于是得到了双指针法的方法一:

方法一 双指针法

ListNode* mergeTwoLists(ListNode* l1,ListNode* l2)
{
    ListNode* hair=new ListNode(-1);

    ListNode* pre=hair;
    while(l1!=nullptr && l2 != nullptr)
    {
        if(l1->val<l2->val)
        {
            pre->next=l1;
            l1=l1->next;
        }
        else{
            pre->next=l2;
            l2=l2->next;
        }
        pre=pre->next;
    }

    pre->next=(l1==nullptr?l2:l1);

    return hair->next;
}

方法二 递归法

很明显,该方法也存在递归解法。通过比较大小,可以解决一个结点的归属,剩下结点就可以直接递归。注意递归出口即可。

该递归比较简单,直接上代码:

ListNode* mergeTwoLists_r(ListNode* l1,ListNode* l2)
{
    if(l1==nullptr) return l2;
    if(l2==nullptr) return l1;

    if(l1->val<l2->val)
    {
        l1->next=mergeTwoLists_r(l1->next,l2);
        return l1;
    }
    else{
        l2->next=mergeTwoLists_r(l1,l2->next);
        return l2;
    }
}

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论