21. 合并两个有序链表(java实现)--2种解法(迭代,递归)LeetCode
2022/2/14 9:11:47
本文主要是介绍21. 合并两个有序链表(java实现)--2种解法(迭代,递归)LeetCode,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 题目:
- 解法1:迭代
- 解法2:递归
题目:
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 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 均按 非递减顺序 排列
解法1:迭代
/** * 思路: * 新建一个节点作为前驱节点,指向新的链表 * 比较list1和list2的值,新链表的next指向小的那个节点,移动节点 * 当list1用完后指向list2 * 当list2用完,反之 */ public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode pre = new ListNode(0); ListNode curr = pre; while (true){ if (list1==null){ curr.next=list2; break; }else if (list2==null){ curr.next=list1; break; } if (list1.val<list2.val){ ListNode next = list1.next; curr.next=list1; curr=list1; list1=next; }else { ListNode next = list2.next; curr.next=list2; curr=list2; list2=next; } } return pre.next; }
时间复杂度:On
空间复杂度:O1
解法2:递归
/** * 思路: * 第一次进入函数:判断list1和list2当前节点谁的值小,作为头节点 * 递归的去找下一个节点 * 当list1用完后直接返回list2 * 当list2用完,反之 */ public ListNode mergeTwoLists(ListNode list1, ListNode list2) { if (list1==null){ return list2; } if (list2==null){ return list1; } if (list1.val>list2.val){ list2.next=mergeTwoLists(list1,list2.next); return list2; }else { list1.next=mergeTwoLists(list1.next,list2); return list1; } }
时间复杂度:On
空间复杂度:On
这篇关于21. 合并两个有序链表(java实现)--2种解法(迭代,递归)LeetCode的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性