牛客网高频算法题系列-BM4-合并两个排序的链表
2022/5/29 1:21:03
本文主要是介绍牛客网高频算法题系列-BM4-合并两个排序的链表,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
牛客网高频算法题系列-BM4-合并两个排序的链表
题目描述
输入两个递增的链表,单个链表的长度为n,合并这两个链表并使新链表中的节点仍然是递增排序的。
- 数据范围: 0 <= n <= 1000,-1000 <= 节点值 <= 1000
- 要求:空间复杂度 O(1),时间复杂度 O(n)
原题目见:BM4 合并两个排序的链表
解法一:链表遍历
- 首先,判断特殊情况,如果链表一为空,直接返回链表二;如果链表二为空,直接返回链表一。
- 否则,先声明一个新的假头结点,然后遍历链表一和链表二,过程如下:
- 如果链表一为空,直接将链表二剩下的结点接到后面,并终止遍历
- 如果链表二为空,直接将链表一剩下的结点接到后面,并终止遍历
- 否则,比较链表一和链表二当前结点的大小,来判断下一个结点,然后处理下一个结点
- 最后,返回合并后的链表。
代码
public class Bm004 { /** * 合并两个排序的链表 * * @param list1 链表一 * @param list2 链表二 * @return */ public static ListNode merge(ListNode list1, ListNode list2) { // 如果链表一为空,直接返回链表二 if (list1 == null) { return list2; } // 如果链表二为空,直接返回链表一 if (list2 == null) { return list1; } // 声明一个新的假头结点 ListNode newList = new ListNode(-1), next = newList; // 遍历链表一和链表二 while (list1 != null || list2 != null) { if (list1 == null) { // 如果链表一为空,直接将链表二剩下的结点接到后面,并终止遍历 next.next = list2; break; } else if (list2 == null) { // 如果链表二为空,直接将链表一剩下的结点接到后面,并终止遍历 next.next = list1; break; } else if (list1.val < list2.val) { // 否则,比较链表一和链表二当前结点的大小,来判断下一个结点,然后处理下一个结点 next.next = list1; list1 = list1.next; } else { next.next = list2; list2 = list2.next; } next = next.next; } // 最后,返回合并后的链表 return newList.next; } public static void main(String[] args) { // 1 -> 3 -> 5 ListNode list1 = ListNode.testCase3(); System.out.println("链表一"); ListNode.print(list1); // 2 -> 4 -> 6 ListNode list2 = ListNode.testCase4(); System.out.println("链表二"); ListNode.print(list2); ListNode newList = merge(list1, list2); System.out.println("合并后的链表"); ListNode.print(newList); } }
\(1.01^{365} ≈ 37.7834343329\)
\(0.99^{365} ≈ 0.02551796445\)
相信坚持的力量!
这篇关于牛客网高频算法题系列-BM4-合并两个排序的链表的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-19永别了,微服务架构!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?