温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

java和java如何实现合并两个有序链表

发布时间:2022-01-17 11:39:59 阅读:166 作者:小新 栏目:大数据
Java开发者专用服务器限时活动,0元免费领,库存有限,领完即止! 点击查看>>

小编给大家分享一下java和java如何实现合并两个有序链表,希望大家阅读完这篇文章之后都有所收获,下面让我们一起去探讨吧!


 

题目描述

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

示例:

输入:1->2->4, 1->3->4输出:1->1->2->3->4->4
   

解题方案

 

思路

  • 标签:链表、递归

  • 这道题可以使用递归实现,新链表也不需要构造新节点,恰好是文章套路解决递归问题的极好验证,我们下面列举递归三个要素

  • 终止条件:两条链表分别名为l1和l2,当l1为空或l2为空时结束

  • 返回值:每一层调用都返回排序好的链表头

  • 本级递归内容:如果l1的val值更小,则将l1.next与排序好的链表头相接,l2同理

  • O(m+n),m为l1的长度,n为l2的长度

 

代码

  • Java版本

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    public ListNode mergeTwoLists(ListNode l1, 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;        }    }}
 
  • JavaScript版本

/** * Definition for singly-linked list. * function ListNode(val) { *     this.val = val; *     this.next = null; * } *//** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */var mergeTwoLists = function(l1, 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;    }};

看完了这篇文章,相信你对“java和java如何实现合并两个有序链表”有了一定的了解,如果想了解更多相关知识,欢迎关注亿速云行业资讯频道,感谢各位的阅读!

亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

原文链接:https://my.oschina.net/u/2446442/blog/4380083

AI

开发者交流群×