合并两个有序的链表(力扣 21)Java递归

简介: 合并两个有序的链表(力扣 21)Java递归

一、题目描述



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


示例 1:

bf769de5f3ab4b26a152de89c189b978.png

输入:l1 = [1,2,4], l2 = [1,3,4]

输出:[1,1,2,3,4,4]


示例 2:

输入:l1 = [], l2 = []

输出:[]


示例 3:

输入:l1 = [], l2 = [0]

输出:[0]

 

提示:

两个链表的节点数目范围是 [0, 50]

-100 <= Node.val <= 100

l1 和 l2 均按 非递减顺序 排列


二、Java代码实现



2.1 递归

     

递归其实不用过多描述了,看代码就能看懂,关键是想不出来……

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        if(list1.val < list2.val){
            list1.next = mergeTwoLists(list1.next, list2);
            return list1;
        } else {
            list2.next = mergeTwoLists(list1, list2.next);
            return list2;
        }
    }
}


时间复杂度:O(M+N)

     

空间复杂度:O(M+N)


2.2 迭代


/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(0);
        ListNode p = head;
        while(list1!=null && list2!=null){
            //把较小的节点接在后面
            if(list1.val <= list2.val){
                p.next = list1;
                list1 = list1.next;
                p = p.next;
            } else {
                p.next = list2;
                list2 = list2.next;
                p = p.next;
            }
        }
        //如果有某个链表还没遍历完,那就直接接在后面
        if(list1!=null){
            p.next = list1;
        }
        if(list2!=null){
            p.next = list2;
        }
        return head.next;
    }
}


时间复杂度:O(M+N)

       

空间复杂度:O(1)

相关文章
|
12月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
129 1
|
12月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
155 0
Leetcode第21题(合并两个有序链表)
|
6月前
|
算法 Go
【LeetCode 热题100】23:合并 K 个升序链表(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 23——合并 K 个升序链表的两种解法:优先队列(最小堆)和分治合并。题目要求将多个已排序链表合并为一个升序链表。最小堆方法通过维护节点优先级快速选择最小值,;分治合并则采用归并思想两两合并链表。文章提供了 Go 语言实现代码,并对比分析两种方法的适用场景,帮助读者深入理解链表操作与算法设计。
196 10
|
12月前
|
存储 算法
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
273 0
java数据结构,双向链表的实现
文章介绍了双向链表的实现,包括数据结构定义、插入和删除操作的代码实现,以及双向链表的其他操作方法,并提供了完整的Java代码实现。
java数据结构,双向链表的实现
|
12月前
|
存储 安全 Java
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
【用Java学习数据结构系列】探索顺序表和链表的无尽秘密(附带练习唔)pro
85 3
|
12月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
126 0
LeetCode第二十四题(两两交换链表中的节点)
|
12月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
138 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
12月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
239 0
|
12月前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
87 0

热门文章

最新文章