LeetCode_21.合并两个有序链表
2024-09-08 06:38:47
LeetCode_21
将两个有序链表合并为一个新的有序链表并返回。
新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
示例代码：
/**
* 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) {
}
}
方法一：使用递归题解
- 测试用例：208个
- 执行用时：1ms
- 内存消耗：35.9MB
- 时间复杂度：O(min(n, m))
- 空间复杂度：O(n+m)
/**
* 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;
} else if (l2 == null) {
return l1;
} else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
}
方法二：使用迭代方法题解
- 测试用例：208个
- 执行用时：1ms
- 内存消耗：36.3MB
- 时间复杂度：O(n+m))
- 空间复杂度：O(1)
/**
* 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) {
// 设置一个哨兵节点
ListNode preHead = new ListNode(-1);
// 指针
ListNode prev = preHead;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}
prev.next = l1 == null ? l2 : l1;
return preHead.next;
}
}
最新文章
- strtok源码 bitset 空间压缩
- 理解 Lua 的那些坑爹特性
- mono中显示debug信息(filename/lineno)
- 【Win10】UAP/UWP (通用程序) 开发初体验(1) 之 开发准备
- Android自动登录与记住密码
- JS控制输入框长度
- iOS界面布局设计
- 理解UIEdgeInsets
- shuffle一个简单的过程叙述性说明
- 711B - Chris and Magic Square 模拟
- oracle取字符串长度的函数length()和hengthb()
- ubuntu下动态链接库的编译和使用实例
- Vue学习之路5-v-model指令
- Pro Git
- react-native 报错 RawText "" must be wrapped in an explicit <Text> component
- centos7 安装zookeeper3.4.8集群
- React Native 学习资料
- 漫画 | Redis常见面试问题（二）
- OpenGL核心技术之帧缓冲
- Linux命令: ls -F