输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
数据范围： 
要求：空间复杂度)
，时间复杂度 )
要求：空间复杂度
例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：
可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
[编程题]两个链表的第一个公共结点
- 热度指数：689552 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
- 算法知识视频讲解
输入描述:
输入分为是3段，第一段是第一个链表的非公共部分，第二段是第二个链表的非公共部分，第三段是第一个链表和第二个链表的公共部分。 后台会将这3个参数组装为两个链表，并将这两个链表对应的头节点传入到函数FindFirstCommonNode里面，用户得到的输入只有pHead1和pHead2。
输出描述:
返回传入的pHead1和pHead2的第一个公共结点，后台会打印以该节点为头节点的链表。
示例1
输入
{1,2,3},{4,5},{6,7}输出
{6,7}说明
第一个参数{1,2,3}代表是第一个链表非公共部分，第二个参数{4,5}代表是第二个链表非公共部分，最后的{6,7}表示的是2个链表的公共部分
这3个参数最后在后台会组装成为2个两个无环的单链表，且是有公共节点的 示例2
输入
{1},{2,3},{}输出
{}说明
2个链表没有公共节点 ,返回null，后台打印{} 说明：本题目包含复杂数据结构ListNode，点此查看相关信息
public class Solution {
public static boolean flag = false;
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode temp = null;
ListNode newHead2 = pHead2;
List<Integer> list = new ArrayList<>();
while (pHead1 != null) {
temp = execute(pHead1, pHead2, temp);
pHead1 = pHead1.next;
}
return temp;
}
public static ListNode execute(ListNode aa, ListNode a, ListNode b) {
if (a != null) {
if (aa == a) {
b = a;
flag = true;
} else {
if(!flag){
b = execute(aa, a.next, b);
}
}
}
return b;
}
}
原来你这个取公共节点取的是公共地址啊
发表于 2024-03-02 17:38:12
回复(0)
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode node1 = pHead1;
ListNode node2 = pHead2;
while(node1 != node2){
if(node1 == null){
node1 = pHead2;
}
else{
node1 = node1.next;
}
if(node2 == null){
node2 = pHead1;
}
else{
node2 = node2.next;
}
}
return node1;
}
编辑于 2023-12-12 19:31:51
回复(0)
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) {
if (pHead1 == null || pHead2 == null) {
return null;
}
if (pHead1.next == pHead2.next) {
return pHead1.next;
}
// if (pHead1 == null && pHead2 != null) {
// return pHead2;
// }
// if (pHead2 == null && pHead1 != null) {
// return pHead1;
// }
ListNode p1 = pHead1;
ListNode p2 = pHead2;
int len1 = 0, len2 = 0;
while (p1 != null) {
len1++;
p1 = p1.next;
}
while (p2 != null) {
len2++;
p2 = p2.next;
}
ListNode frist = len1 > len2 ? pHead1 : pHead2;
ListNode slow = frist == pHead1 ? pHead2 : pHead1;
int k = Math.abs(len1 - len2);
System.out.println(k);
for (int i = 0; i < k; i++) {
frist = frist.next;
}
while (slow != frist) {
frist = frist.next;
slow = slow.next;
}
return frist;
}
} 求大神指点，为啥这个案例不过啊？？？？？？？？？？
发表于 2023-12-04 22:24:26
回复(1)
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null || pHead2 ==null){
return null;
}
ListNode res = new ListNode(-1);
ListNode temp = res;
ListNode temp1 = ReverseNode(pHead1);
ListNode temp2 = ReverseNode(pHead2);
while(temp1==temp2){
res.next = temp1;
res = res.next;
temp1 = temp1.next;
temp2 = temp2.next;
}
ListNode result = ReverseNode(temp.next);
return result;
}
public ListNode ReverseNode(ListNode head){
if(head==null || head.next==null){
return head;
}
// 先反转 head->next 后面的链表
ListNode res = ReverseNode(head.next);
// 再反转 head 节点
head.next.next = head;
head.next = null;
// 返回反转后的头节点
return res;
}
}
发表于 2023-10-03 12:39:14
回复(0)
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) {
Set<ListNode> sets=new HashSet<>();
while(pHead1!=null){
sets.add(pHead1);
pHead1=pHead1.next;
}
while(pHead2!=null){
if(sets.contains(pHead2)){
return pHead2;
}
pHead2=pHead2.next;
}
return null;
}
}
发表于 2023-09-21 18:19:11
回复(0)
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode p1 = pHead1;
ListNode p2 = pHead2;
while (true) {
if (p1 == p2) return p1;
p1 = (p1 == null) ? pHead2 : p1.next;
p2 = (p2 == null) ? pHead1 : p2.next;
}
}
}
发表于 2023-08-07 21:51:29
回复(0)
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) {
return null;
}
if (pHead1 == pHead2) return pHead1;
int n1 = 0;
int n2 = 0;
ListNode h1 = pHead1;
ListNode h2 = pHead2;
while (pHead1.next != null || pHead2.next != null) {
if (pHead1.next != null && pHead2.next != null) {
pHead1 = pHead1.next;
pHead2 = pHead2.next;
if (pHead1 == pHead2) return pHead1;
} else if (pHead1.next == null) {
pHead2 = pHead2.next;
n2++;
} else {
pHead1 = pHead1.next;
n1++;
}
}
if (pHead1 != pHead2) return null;
if (n1 > 0) {
while (h1.next != null) {
if (n1 > 0) {
h1 = h1.next;
n1--;
} else {
h1 = h1.next;
h2 = h2.next;
}
if (h1 == h2) return h1;
}
} else if (n2 > 0) {
while (h2.next != null) {
if (n2 > 0) {
h2 = h2.next;
n2--;
} else {
h1 = h1.next;
h2 = h2.next;
}
if (h1 == h2) return h1;
}
}
return null;
}
思路感觉差不多，大神的代码更简洁
发表于 2023-07-18 11:00:03
回复(0)
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
//两个链表的相遇，走完自己走别人
ListNode cur1=pHead1;
ListNode cur2=pHead2;
while(cur1!=cur2){//直到找到公共节点
if(cur1!=null) {
cur1=cur1.next;
}else{
cur1=pHead2;
}
if(cur2!=null){
cur2=cur2.next;
}else{
cur2=pHead1;
}
}
return cur1;
}
发表于 2023-07-17 19:52:04
回复(0)
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) {
if (pHead1 == null || pHead2 == null) {
return null;
}
//2、计算链表的长度
int lenA = 0;
int lenB = 0;
ListNode curA = pHead1;
ListNode curB = pHead2;
while (curA != null) {
lenA++;
curA = curA.next;
}
while (curB != null) {
lenB++;
curB = curB.next;
}
curA = pHead1;
curB = pHead2;
int len = lenA - lenB;
if (len > 0) {
while (len-- > 0) {
curA = curA.next;
}
} else {
len = -len;
while (len-- > 0) {
curB = curB.next;
}
}
while (curA != null) {
if (curA == curB) {
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
发表于 2023-07-10 12:42:24
回复(0)
两种，一种 HashSet 去重
import java.util.Set;
import java.util.HashSet;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
// 使用 HashSet 去重的解法
Set<ListNode> nodes = new HashSet<>();
ListNode tmp = pHead1;
while (tmp!=null && nodes.add(tmp)) {
tmp = tmp.next;
}
tmp = pHead2;
while (tmp!=null && nodes.add(tmp)) {
tmp = tmp.next;
}
return tmp;
}
} 第二种就是获得两个链表的长度，较长的链表从差值处开始遍历，较短的链表从头开始遍历，每次向后移动时比较是否为公共节点 public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
// 遍历两个链表，求节点差异，然后比较可能的公共节点是否一致
if (pHead1==null || pHead2==null) {
return null;
}
// 获取两个链表的节点数量
int len1 = 0;
int len2 = 0;
ListNode tmp1 = pHead1;
ListNode tmp2 = pHead2;
while (tmp1 != null) {
++len1;
tmp1 = tmp1.next;
}
while (tmp2 != null) {
++len2;
tmp2 = tmp2.next;
}
tmp1 = pHead1;
tmp2 = pHead2;
// 节点多的链表向前移动
if (len1 > len2) {
for (int i=0; i<len1-len2; ++i) {
tmp1 = tmp1.next;
}
} else {
for (int i=0; i<len2-len1; ++i) {
tmp2 = tmp2.next;
}
}
// 移动至链表尾，发现一致的返回
while (tmp1 != null) {
if (tmp1 == tmp2) {
return tmp1;
}
tmp1 = tmp1.next;
tmp2 = tmp2.next;
}
return null; // 美哟公共节点
}
}
发表于 2023-06-11 21:23:56
回复(0)
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null||pHead2==null) return null;
ListNode p=pHead1,q=pHead2;
for(p=pHead1;p!=null;p=p.next){
for(q=pHead2;q!=null;q=q.next){
if(q.val==p.val&&q==p) {
return p;
}
}
}
return null;
}
}
发表于 2023-05-23 09:27:38
回复(0)
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
//Haseset来存，遇到一样的就返回
import java.util.HashSet;
import java.util.Set;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
Set<ListNode> set = new HashSet<>();
ListNode publicNode = null;
while (pHead1 != null) {
set.add(pHead1);
pHead1 = pHead1.next;
}
while (pHead2 != null) {
if (set.contains(pHead2)) {
publicNode = pHead2;
break;
}
set.add(pHead2);
pHead2 = pHead2.next;
}
return publicNode;
}
}
发表于 2023-03-26 19:32:17
回复(0)
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
HashSet<ListNode> hashSet = new HashSet();
while(pHead1!=null||pHead2!=null){
if(pHead1!=null){
if(!hashSet.add(pHead1))
return pHead1;
pHead1 = pHead1.next;
}
if(pHead2!=null){
if(!hashSet.add(pHead2))
return pHead2;
pHead2 = pHead2.next;
}
}
return null;
}
}
发表于 2023-02-25 15:52:54
回复(0)
/*
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;
ListNode p2 = pHead2;
while(p1 != p2) {
if(p1 == null) {
p1 = pHead1;
} else {
p1=p1.next;
}
if(p2 == null) {
p2 = pHead2;
} else{
p2 = p2.next;
}
}
return p1;
}
}
发表于 2023-01-18 23:37:04
回复(0)
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int length1=length(pHead1);
int length2=length(pHead2);
if(length1==0 || length2==0){
return null;//如果有一个链表的长度为0,则返回Null
}
if(length1>length2){
//如果链表1长度大于链表2，则让链表1的头节点后移gap次
int gap=length1-length2;
for(int i=0;i<gap;i++){
pHead1=pHead1.next;
}
}else{
//如果链表2长度大于链表1，则让链表2的头节点后移gap次
int gap=length2-length1;
for(int i=0;i<gap;i++){
pHead2=pHead2.next;
}
}
//最后同时后移，如果pHead1==pHead2,则返回公共节点pHead2
while(pHead1!=pHead2){
pHead1=pHead1.next;
pHead2=pHead2.next;
}
return pHead1;
}
public int length(ListNode head){
//计算链表的长度
int length=0;
while(head!=null){
head=head.next;
length++;
}
return length;
}
}
发表于 2022-11-09 17:29:14
回复(0)
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
//思路为：
//1、先算出两个链表的长度
//2、然后计算出差值，让长链表先走差值的步数
//3、两链表再一起走直到遇到相同的节点，则此节点为重合部分的入口节点
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) {
return null;
}
int c1 = 0;
int c2 = 0;
ListNode temp1 = pHead1;
ListNode temp2 = pHead2;
while (temp1 != null) {
c1++;
temp1 = temp1.next;
}
while (temp2 != null) {
c2++;
temp2 = temp2.next;
}
int diff = 0;
int index = 0;
if (c1 >= c2) {
diff = c1 - c2;
while (index != diff) {
index++;
pHead1 = pHead1.next;
}
} else {
diff = c2 - c1;
while (index != diff) {
index++;
pHead2 = pHead2.next;
}
}
while (pHead1 != null && pHead2 != null) {
if (pHead1 == pHead2) {
return pHead1;
}
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
return null;
}
}
发表于 2022-10-21 07:00:58
回复(0)
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if(pHead1==null||pHead2==null)
return null;
ListNode head=pHead1;
while(head!=null){ //链表一的结点，
ListNode head2=pHead2;
while(head2!=null){ //链表二的节点，依次遍历与链表一的节点对比。
if(head==head2)
return head;
head2=head2.next;
}
head=head.next;
}
return null;
}
}
暴力依次对比
发表于 2022-09-30 00:45:13
回复(0)
问题信息
难度：
232条回答
2425收藏
128049浏览
通过挑战的用户
查看代码-
2023-03-14 10:58:05 -
2023-03-10 16:30:41
-
2023-03-09 17:20:34
-
2023-02-27 22:56:47
-
2023-02-16 14:00:55
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
/* 找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走 （因为2个链表用公共的尾部） */ class Solution { public: ListNode* FindFirstCommonNode( ListNode *pHead1, ListNode *pHead2) { int len1 = findListLenth(pHead1); int len2 = findListLenth(pHead2); if(len1 > len2){ pHead1 = walkStep(pHead1,len1 - len2); }else{ pHead2 = walkStep(pHead2,len2 - len1); } while(pHead1 != NULL){ if(pHead1 == pHead2) return pHead1; pHead1 = pHead1->next; pHead2 = pHead2->next; } return NULL; } int findListLenth(ListNode *pHead1){ if(pHead1 == NULL) return 0; int sum = 1; while(pHead1 = pHead1->next) sum++; return sum; } ListNode* walkStep(ListNode *pHead1, int step){ while(step--){ pHead1 = pHead1->next; } return pHead1; } };