Shulou(Shulou.com)06/01 Report--

小编给大家分享一下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如何实现合并两个有序链表"有了一定的了解，如果想了解更多相关知识，欢迎关注行业资讯频道，感谢各位的阅读!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.