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

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

22 人参与  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://zhangshiyu.com/post/30305.html

<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

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

最新文章

  • (番外)+(全书)***顾时(像春天原谅了所有雪全书+后续)全书在线_***顾时免费列表_笔趣阁(像春天原谅了所有雪全书+后续)
  • [老公拿我狐尾哄白月光后,悔疯了]章节限时抢先看‌_周怀瑾白月光明白完整版在线阅读
  • 日暮青山绿渐隐(纪冰雪许星森)全书浏览_日暮青山绿渐隐全书浏览
  • 纪冰雪许星森+后续+结局(纪冰雪许星森)列表_纪冰雪许星森+后续+结局(纪冰雪许星森)纪冰雪许星森+后续+结局在线
  • 日暮青山绿渐隐结局+番外+完本(纪冰雪许星森)列表_日暮青山绿渐隐结局+番外+完本(纪冰雪许星森)日暮青山绿渐隐结局+番外+完本在线
  • 全文半是风雨半是霜+后续+结局(顾宴辞宋相欢)列表_全文半是风雨半是霜+后续+结局
  • 黎落封屿沈绝后续+结局列表_黎落封屿沈绝后续+结局
  • 完结文阮雾梨谢昀川闻砚辞+后续+结局列表_完结文阮雾梨谢昀川闻砚辞+后续+结局(谢昀川闻砚辞阮雾梨)
  • 像春天原谅了所有雪免费赏析全书顾时***在线
  • 穿成古代医仙,开局救下太守千金小说精彩节选免费试读_方岐柳潇湘番外合集提前订‌
  • 等风等雨等不到你结局+番外_(夏语栀祁墨寒)等风等雨等不到你结局+番外列表_笔趣阁(夏语栀祁墨寒)
  • 重生之我变懒后,夫家更看重!+番外+后续(姜姩祁珩)_重生之我变懒后,夫家更看重!+番外+后续

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

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