【每日一题】【遍历orSet】2022年2月1日-NC66 两个链表的第一个公共结点
2024-09-08 19:10:28
描述
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
输入描述：
输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。
返回值描述：
返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。
方法1：使用Set存结点
import java.util.*;
/*
public class ListNode {
int val;
ListNode next = null; ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode p1 = pHead1, p2 = pHead2;
Set<ListNode> set = new HashSet<>();
while(p1 != null) {
set.add(p1);
p1 = p1.next;
}
while(p2 != null) {
if(set.contains(p2)) {
return p2;
}
p2 = p2.next;
}
return null;
}
}
方法2：使用暴力，对p1的每个节点，均遍历一次p2
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) {
return null;
}
ListNode firstNode = pHead2;
for (; pHead1 != null; pHead1 = pHead1.next) {
if (pHead2 == null) {
pHead2 = firstNode;
}
for (; pHead2 != null; pHead2 = pHead2.next) {
if (pHead1 == pHead2) {
return pHead1;
}
}
}
return null;
}
最新文章
- 关于docker
- cookie小析
- java 读取文件最佳实践
- POJ 1269 Intersecting Lines（直线相交判断，求交点）
- c#多层嵌套Json
- C 实现的算法篇
- LoadRunner监控Windows和Linux常见问题
- JS_全
- Android View框架总结（二）View焦点
- response.redirect 与location.href 的区别
- asyncio异步IO--协程（Coroutine）与任务(Task)详解
- Python面试题目之Python函数默认参数陷阱
- ThinkAdmin for PHP后台管理系统
- 枚举getClass、getDeclaringClass区别
- Confluence 6 管理协同编辑 - 代理和 SSL 的考虑
- IDEA git修改远程仓库地址
- Python: 列表，元组，字典的区别
- Rafy中的IOC
- python3 把excel文件合并并保存到csv文件
- 在不指定特殊属性的情况下，哪几种HTML标签可以手动输入文本：（）