当前位置:首页 » 《休闲阅读》 » 正文

【链表面试题】合并两个有序链表_C->顾某的博客

20 人参与  2022年02月08日 11:09  分类 : 《休闲阅读》  评论

点击全文阅读


目录

题目描述

思路一

思路二


​​​​​​​

​​​​​​​

题目描述

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


 

思路一

1.可以定义一个指针指向L1的头节点,定义一个指针指向L2的头节点。拿L1中的val和L2的val进行对比,小的数值的节点尾插到新链表中,并让该节点指向下一个节点。

2.若L1或L2其中一个已经指向空,但另一个不为空,则直接将新链表的尾指针指向L1或L2中不为空的那个节点。

3.代码如下:

/**
 * 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* head=(struct ListNode*)malloc(sizeof(struct ListNode)) , *t =head; //创建一个头节点
     while(l1!=NULL&&l2!=NULL)
     {
        if(l1->val<l2->val)
         {
             t->next=l1;      
             l1=l1->next;
         }
        else
         {
             t->next=l2;
             l2=l2->next;
         }
         t=t->next;
     }
     if(l1==NULL)
     {
         t->next=l2;
     }
     else
     {
         t->next=l1;
     }
     struct ListNode* List=head->next; //为了释放创建的头节点
     free(head);
     return List;
}

 

思路二

1.思路二主要是用递归的方式,虽然代码量比思路一要少,但是思路不好想,代码不容易看懂,如果看懂了思路一的同学,可以看看思路二。

2.首先找递归体,取L1和L2小的那一个,如果是L1小,则递归(L1->next,L2)

3.终止递归的条件:若L1或L2其中一个为空,则返回另一个。

4.代码如下: 

/**
 * 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;
    if(l1->val<l2->val){
        l1->next = mergeTwoLists(l1 ->next,l2);
        return l1; 
    }else{
        l2->next = mergeTwoLists(l1,l2->next);
        return l2;
    }
 

总结

1.本文主要是讲解合并两个有序链表的两个基本思路,如果是初学链表的同学可以,多研究思路一,如果对链表已经有些掌握的同学可以多研究思路二。

2.最后,也请大家多多支持,求关注!!!


点击全文阅读


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

节点  思路  递归  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

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

最新文章

  • 她的记忆停留在了最爱初恋的那年许欣柔楚临川完本_她的记忆停留在了最爱初恋的那年(许欣柔楚临川)
  • 全书浏览假千金的实习生男友霸占我办公室,我反手让他们倾家荡产(顾家明)_假千金的实习生男友霸占我办公室,我反手让他们倾家荡产(顾家明)全书结局
  • 童养夫让我给他的新欢出修复费(林嘉芝林思雅)_童养夫让我给他的新欢出修复费林嘉芝林思雅
  • 全文资助生女婿让我给他白月光付三千万月子中心钱(宋清玉宋雅)列表_全文资助生女婿让我给他白月光付三千万月子中心钱
  • 碎在时光里的谎言喻景宴秦明月完本_碎在时光里的谎言(喻景宴秦明月)
  • 旧爱剜心吻成灰席鄢之岑秋全书免费旧爱剜心吻成灰席鄢之岑秋全书免费
  • 结婚六年丈夫不碰我谁知儿子亲爹是寡头(纪清言傅司砚),结婚六年丈夫不碰我谁知儿子亲爹是寡头
  • 老公想换掉我的男胎,我笑他自不量力(宋薇于继业)_老公想换掉我的男胎,我笑他自不量力宋薇于继业
  • 给太子下了噬心蛊后,皇后找上门(小夭赵劼)全书浏览_给太子下了噬心蛊后,皇后找上门全书浏览
  • 豪门绝嗣!带球跑的夫人回来了!(谢长宴慕清杳)_豪门绝嗣!带球跑的夫人回来了!谢长宴慕清杳
  • 完美身材(李朵林之晴)_完美身材李朵林之晴
  • 离婚后,我和快穿系统绑定(白意秋陈荣周立慧)_离婚后,我和快穿系统绑定(白意秋陈荣周立慧)

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

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