经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » 编程经验 » 查看文章
21. 合并两个有序链表
来源:cnblogs  作者:fuxing.  时间:2024/6/13 9:41:28  对本文有异议

题目链接

一、题目描述

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]

3. 提示

  • 两个链表的节点数目范围是[0, 50]
  • l1 和 l2 均按非递减顺序排列
  • -100 <= Node.val <= 100

二、代码实现

1. 递归

1.1 解题思路

链表、树、图相关的算法首先想递归。递归相关的知识见我的另一篇文章迭代与递归

递归设计函数的步骤:
1. 找重复: 找到的相同的子问题。

如下图,可以得出子问题为,l1 和 l2 当前节点的不断比较,当然,这里的当前节点是需要不断变化的。

2. 找变化:聚焦于某一个子问题,查看变化的量,通常会作为参数,这时可定义函数体。

由于当前节点的比较是不断变化的,所以这里变化的量我们就需要分情况讨论了,如下图,可总结为小的往前走一步,继续跟大的比

总结完情况,则进行代码实现:

  1. public ListNode mergeTwoLists (ListNode listNode1, ListNode listNode2) {
  2. if(listNode1.val < listNode2.val){
  3. listNode1.next = mergeTwoLists(listNode1.next,listNode2);
  4. return listNode1;
  5. }else {
  6. listNode2.next = mergeTwoLists(listNode1,listNode2.next);
  7. return listNode2;
  8. }
  9. }

3. 找出口: 也就是找终止条件。

什么时候无法比较当前节点的值,这个比较好找,就是当 listNode1 的为 null,或者 listNode2 为 null 时,无法进行比较了,可直接返回对应有值的节点,代码如下。

  1. public ListNode mergeTwoLists (ListNode listNode1, ListNode listNode2) {
  2. if (listNode1 == null) {
  3. return listNode2;
  4. } else if (listNode2 == null) {
  5. return listNode1;
  6. } else if (listNode1.val < listNode2.val) {
  7. listNode1.next = mergeTwoLists(listNode1.next, listNode2);
  8. return listNode1;
  9. } else {
  10. listNode2.next = mergeTwoLists(listNode1, listNode2.next);
  11. return listNode2;
  12. }
  13. }

1.2 复杂度分析

时间复杂度 O(m+n),m、n 分别为链表的长度,因为每次调用递归都会去掉 listNode1 或者 listNode2 的头节点(直到至少有一个链表为空),则最多只会递归调用每个节点一次。因此,时间复杂度取决于合并后的链表长度,即 O(m+n)。
空间复杂度 O(m+n),m、n 分别为链表的长度,递归需要消耗栈空间且大小取决于递归调用的深度。结束递归调用时最多调用 m+n 次,因此空间复杂度为 O(m+n)。

2. 迭代

2.1 解题思路

迭代与递归基本都是可以互转的,与递归类似,我们将两个链表的比较理解为指针的移动。

这里我们还需要一个哨兵节点,为什么需要哨兵节点呢,我们在遍历链表的过程中是不断的调整它的 next 指针,当我们遍历到最后时,哨兵节点更容易返回合并后的链表,过程如下图。

通过图解,可以了解迭代的大致流程,但是我们在 Java 代码实现时,还需要维护一个 prev 指针,用来调整它的 next 指针。

为什么需要这个指针而不是直接返回哨兵节点呢?原因是我们在不断的遍历中,指针会不断的下移,当我们合并完成所有的节点时,此时的指针是在最后,这时我们在获取合并后的链表就比较麻烦了。

而用一个 prev 指针代替哨兵节点去进行 next 指针的移动,当返回链表时,只需返回哨兵节点的 next 即可。

代码实现如下:

  1. public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
  2. // 哨兵节点的设置
  3. ListNode prehead = new ListNode(-1);
  4. // 维护 prev 指针进行移动
  5. ListNode prev = prehead;
  6. while (list1 != null && list2 != null) {
  7. // 值比较,小的接入哨兵节点,并往前走一步,继续与大的比较
  8. if (list1.val < list2.val) {
  9. prev.next = list1;
  10. list1 = list1.next;
  11. }
  12. else {
  13. prev.next = list2;
  14. list2 = list2.next;
  15. }
  16. // 指针移动到 next,为了后续的节点接入
  17. prev = prev.next;
  18. }
  19. // 三元运算,当 list1 或 list2 出现 null 时,非 null 的则可以直接接入哨兵节点
  20. prev.next = list1 != null ? list1 : list2;
  21. return prehead.next;
  22. }

2.2 复杂度分析

时间复杂度 O(m+n),m、n 分别为链表的长度,合并操作只需遍历链表。
空间复杂度 O(1),prehead、prev 均只使用常数大小的内存空间。

原文链接:https://www.cnblogs.com/fuxing/p/18245251

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号