牛客网高频算法题系列-BM10-两个链表的第一个公共结点
2022/6/4 1:22:28
本文主要是介绍牛客网高频算法题系列-BM10-两个链表的第一个公共结点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
牛客网高频算法题系列-BM10-两个链表的第一个公共结点
题目描述
输入两个无环的单向链表,找出它们的第一个公共结点,如果没有公共节点则返回空。(注意因为传入数据是链表,所以错误测试数据的提示是用其他方式显示的,保证传入数据是正确的)
原题目见:BM10 两个链表的第一个公共结点
解法一:双重循环
使用双重循环遍历2个链表,简单粗暴,不过效率稍低。
解法二:双指针法
使用2个指针l1和l2分别从链表一和链表二的头结点遍历,遍历到尾部后,再分别从链表二和链表一遍历,如果两个链表有公共交点,则l1和l2一定会在交点处相遇,否则,l1和l2分别遍历完两个链表后都是null,没有公共结点。
代码
public class Bm010 { /** * 方法一:双重循环 * * @param pHead1 链表一 * @param pHead2 链表二 * @return */ public static ListNode findFirstCommonNode(ListNode pHead1, ListNode pHead2) { if (pHead1 == null || pHead2 == null) { return null; } ListNode node1 = pHead1; // 外层循环遍历链表一的结点 while (node1 != null) { ListNode node2 = pHead2; // 内层循环遍历链表二的结点 while (node2 != null) { if (node2 == node1) { return node1; } node2 = node2.next; } node1 = node1.next; } return null; } /** * 双指针法 * * @param pHead1 * @param pHead2 * @return */ public static ListNode findFirstCommonNode2(ListNode pHead1, ListNode pHead2) { // l1和l2分别从链表一和链表二的头结点遍历,遍历到尾部后,再分别从链表二和链表一遍历 ListNode l1 = pHead1, l2 = pHead2; while (l1 != l2) { l1 = (l1 == null) ? pHead2 : l1.next; l2 = (l2 == null) ? pHead1 : l2.next; } // 如果两个链表有公共交点,则l1和l2一定会在交点处相遇,此时l1就是公共结点 // 否则,l1和l2分别遍历完两个链表后都是null,没有公共结点,返回null return l1; } public static void main(String[] args) { ListNode pHead1 = ListNode.testCase2(); System.out.println("链表一为"); ListNode.print(pHead1); ListNode pHead2 = ListNode.testCase1(); pHead2.next.next.next = pHead1.next.next; System.out.println("链表二为"); ListNode.print(pHead2); ListNode.print(findFirstCommonNode(pHead1, pHead2)); ListNode.print(findFirstCommonNode2(pHead1, pHead2)); } }
\(1.01^{365} ≈ 37.7834343329\)
\(0.99^{365} ≈ 0.02551796445\)
相信坚持的力量!
这篇关于牛客网高频算法题系列-BM10-两个链表的第一个公共结点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?