当前位置:首页 » 《资源分享》 » 正文

【力扣LeetCode】合并两个有序链表_Layman光~的博客

14 人参与  2021年10月31日 11:43  分类 : 《资源分享》  评论

点击全文阅读


题目:

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
在这里插入图片描述

题目分析:

在这里插入图片描述
解决这个问题的方法是,可以将两个链表中的数据依次比较,然后我们可以将较小的取下来尾插,就这样依次进行,直到其中一个走到空,就可以结束了。

代码实现:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;
    struct ListNode*n1,*n2;
    n1 = l1;
    n2 = l2;
    struct ListNode*newhead,*tail;
    newhead = tail = NULL;
    while(n1 && n2)
    {
        if(n1->val<n2->val)
        {
            if(tail == NULL)
            {
                newhead = tail = n1;
            }
            else
            {
                tail->next = n1;
                tail = n1;
            }
            n1 = n1->next;
        }
        else
        {
            if(tail == NULL)
            {
                newhead = tail = n2;
            }
            else
            {
                tail->next = n2;
                tail = n2;
            }
            n2 = n2->next;
        }
    }
    if(n1)
    {
        tail->next = n1;
    }
    if(n2)
    {
        tail->next = n2;
    }
    return newhead;

}

优化方案:

看上面的代码,我们可能会发现其中的循环有点冗余,因此我们可以改进一下,我们可以在这两个链表中首先比较找出一个较小的值作为头节点,然后进行尾插;我们还可以用一个带哨兵位的头节点来解决这个问题。下面我们就分别给出两端优化的代码:

struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;
    struct ListNode*n1,*n2;
    n1 = l1;
    n2 = l2;
    struct ListNode*newhead,*tail;
    newhead = tail = NULL;
    //先取一个小的做头节点
    if(n1->val < n2->val)
    {
        newhead = tail = n1;
        n1 = n1->next;
    }
    else
    {
        newhead = tail = n2;
        n2 = n2->next;
    }
    while(n1 && n2)
    {
        if(n1->val<n2->val)
        {
            tail->next = n1;
            tail = n1;
            n1 = n1->next;
        }
        else
        {
            tail->next = n2;
            tail = n2;
            n2 = n2->next;
        }
    }
    if(n1)
    {
        tail->next = n1;
    }
    if(n2)
    {
        tail->next = n2;
    }
    return newhead;

}
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2){
    if(l1 == NULL)
        return l2;
    if(l2 == NULL)
        return l1;
    struct ListNode*n1,*n2;
    n1 = l1;
    n2 = l2;
    struct ListNode*newhead,*tail;
    newhead = tail = NULL;
    //给一个哨兵位的头节点,方便尾插,处理完以后,再删掉。
    newhead = tail = (struct ListNode*)malloc(sizeof(struct ListNode));
    while(n1 && n2)
    {
        if(n1->val<n2->val)
        {
            tail->next = n1;
            tail = n1;
            n1 = n1->next;
        }
        else
        {
            tail->next = n2;
            tail = n2;
            n2 = n2->next;
        }
    }
    if(n1)
    {
        tail->next = n1;
    }
    if(n2)
    {
        tail->next = n2;
    }
    struct ListNode* first = newhead->next;
    free(newhead);
    return first;

}

点击全文阅读


本文链接:http://m.zhangshiyu.com/post/30305.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • 谢承钧小说整本+后续(穿成佛子的恶毒后妈)清爽版阅读
  • 你惹她干啥她疯起来嘎乱杀结局+番外+完结(楚瑶)全书浏览_你惹她干啥她疯起来嘎乱杀结局+番外+完结全书浏览
  • 清冷逆徒动情后,反派师尊被缠哭(洛凝墨寒砚)_清冷逆徒动情后,反派师尊被缠哭
  • 高考分数出来那天,全家哭着求我原谅后续+番外_何思涵妹妹何思墨未删减_小说后续在线阅读_无删减免费完结_
  • 婚礼前夜未婚夫喂我安眠药,只为让养妹当新娘独家番外_许绍宁养妹全文_小说后续在线阅读_无删减免费完结_
  • 以身入局,我要掀翻这座城的天结局+番外+续集(程少云阮朵)_以身入局,我要掀翻这座城的天结局+番外+续集(程少云阮朵)
  • 出狱后,真千金手撕白莲杀疯了全文免费阅读无弹窗大结局_秦季姜沁最新章节列表_笔趣阁(出狱后,真千金手撕白莲杀疯了:完结+结局+番外)
  • 似锦的夫君停妻另娶挚友遗孀后,我杀疯了贺朝朝贺凌洲全书在线
  • 今夜雨将至(安佩项齐晟)_今夜雨将至
  • 暗恋逢光(江司聿夏未央)全书浏览_暗恋逢光全书浏览
  • 全文季总他图谋已久列表(秦韵季野)列表_全文季总他图谋已久列表
  • 重回高考前一天,我不再阻止同学们去参加班花组织的成人礼高口碑_林绾绾绾孟瑶故事会_小说后续在线阅读_无删减免费完结_

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1