合并两个有序的链表(力扣 21)Java递归
2023-03-14 22:54:27 时间
一、题目描述
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入: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)
相关文章
- Go---Go并发编程(详细)(一)
- Go---Go并发编程(详细)(二)
- Go---Go并发编程(详细)(三)
- Java 日期时间与正则表达式
- 硬核!万人围观,Java时间工具类,无法拒绝
- IDEA 添加 Tomcat,有图易懂
- Tomcat 配置环境变量,有图易懂
- golang 协程并发代码 demo
- Java 判断list是否为空,有图易懂
- Java 最常见的面试题:== 和 equals 的区别是什么
- 【JAVA定时器】四种常见定时器的原理和简单实现,有图易懂 上
- 【JAVA定时器】四种常见定时器的原理和简单实现,有图易懂 中
- 【JAVA定时器】四种常见定时器的原理和简单实现,有图易懂 下
- Java 最常见的面试题:两个对象的 hashCode()相同,则 equals()也一定为 true,对吗?
- Java 最常见的面试题:final 在 java 中有什么作用
- Java后端,正则匹配
- 【运维】阿里云宝塔面板部署JavaWeb项目
- JVM笔记
- 《java并发编程实战》总结(一)
- 二叉树的镜像(剑指offer 27)Java递归(dfs)+辅助栈两种方法实现