前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >21.合并两个有序链表

21.合并两个有序链表

作者头像
魚迹
发布2023-05-06 21:27:44
2020
发布2023-05-06 21:27:44
举报

LeetCode-21.合并两个有序链表

1、题目描述

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

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

示例2: 输入:l1 = [], l2 = [] 输出:[]

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

2、解题思路

思路1: 直接遍历比较两个链表的元素值,并使用尾插法将小值插入新链表中。

思路1步骤如下: 1、判断两个链表是否有空链,有空则直接返回非空链表。 2、循环遍历:当两个链表结点都不为空时,比较结点值大小,小值以尾插法插入新链表 3、当有一链表遍历至结尾为空时,将另一链表剩余结点链接到新链表尾部 4、返回新链表

思路2: 使用递归,合并有序链表,具体代码见下方。 题外话:递归的思路借鉴了他人的题解,看到别人的解题思路,不得不感叹,自己就是个小菜鸡,大佬的代码看起来真赏心悦目。

3、代码实现

代码语言:javascript
复制
//思路1代码如下
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode *L ,*r,*s;
    L = (struct ListNode *)malloc(sizeof(struct ListNode));
    L->next = NULL;
    r =L;
    if(list1 == NULL)
    {
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }
    while(list1 != NULL && list2 != NULL)
    {
        if(list1->val <= list2->val)
        {
            s = (struct ListNode *)malloc(sizeof(struct ListNode));
            s->val = list1->val;
            r->next= s;
            r = s;
            list1 = list1->next; 
        }
        else
        {
            s = (struct ListNode *)malloc(sizeof(struct ListNode));
            s->val = list2->val;
            r->next= s;
            r = s;
            list2 = list2->next;
        }
    }
    while(list1 != NULL)
    {
        s = (struct ListNode *)malloc(sizeof(struct ListNode));
        s->val = list1->val;
        r->next= s;
        r = s;
        list1 = list1->next;
    }
     while(list2 != NULL)
    {
        s = (struct ListNode *)malloc(sizeof(struct ListNode));
        s->val = list2->val;
        r->next= s;
        r = s;
        list2 = list2->next;
    }
    r->next = NULL;
    return L->next;
}
代码语言:javascript
复制
//思路二代码
//(1)自己写的递归代码如下
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    struct ListNode *L;
    L = (struct ListNode *)malloc(sizeof(struct ListNode));
    L->next = NULL;
    if(list1 == NULL)
    {
        return list2;
    }
    if(list2 == NULL)
    {
        return list1;
    }
   if(list1->val <= list2->val)
   {
       L->val = list1->val;
       L->next = mergeTwoLists(list1->next,list2);
       return L;
   }else
   {
       L->val = list2->val;
       L->next = mergeTwoLists(list1,list2->next);
       return L;
   }
}


//(2)借鉴递归题解代码如下
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
    if(list1 == NULL)
        return list2;
    if(list2 == NULL)
        return list1;
   if(list1->val <= list2->val)
   {
       list1->next = mergeTwoLists(list1->next,list2);
       return list1;
   }else
   {
       list2->next = mergeTwoLists(list1,list2->next);
       return list2;
   }
}

4、解题记录

在解决本题时最初的思路就是通过遍历比较值的大小然后合并两个链表,并且由于对于链表知识的遗忘,导致具体实现过程中出现一些错误,且时间花费在复习链表知识上。后来成功提交后,看了题解,才发现可以使用递归解决该题目,并自己尝试着写递归,能成功提交,但占用内存相比官方递归代码多。 第一次提交: 遍历比较值,合并链表,结果如下所示

在这里插入图片描述
在这里插入图片描述

第二次提交: 自己写的递归,结果如下

在这里插入图片描述
在这里插入图片描述

第三次提交: 官方递归,结果如下

在这里插入图片描述
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2023-01-13,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • LeetCode-21.合并两个有序链表
  • 1、题目描述
  • 2、解题思路
  • 3、代码实现
  • 4、解题记录
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档