输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
数据范围： 
要求：空间复杂度)
，时间复杂度 )
要求：空间复杂度
例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：
可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
[编程题]两个链表的第一个公共结点
- 热度指数：735935 时间限制：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，点此查看相关信息
弱智写法，扫完链表1再扫链表2
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
// write code here
while(pHead1) {
pHead1.visited = true
pHead1 = pHead1.next
}
while(pHead2) {
if(pHead2.visited) {
return pHead2
}
pHead2 = pHead2.next
}
return null
}
module.exports = {
FindFirstCommonNode : FindFirstCommonNode
};
发表于 2025-02-09 15:38:43
回复(1)
但是谁能告诉我，这个解法为什么不行？经常说超时。然后我放到本地调试，发现即便p1和p2已经走到了相遇的地方，但是while循环依然没停。。。。请问是什么原因呢呢呢？？？
function FindFirstCommonNode(pHead1, pHead2) {
// write code here
if (pHead1 == null || pHead2 == null) {
return null;
}
let p1 = pHead1;
let p2 = pHead2;
while (p1 != p2) {
p1 = p1.next == null ? pHead2 : p1.next;
p2 = p2.next == null ? pHead1 : p2.next;
}
return p1;
}
发表于 2024-07-20 11:08:29
回复(0)
function FindFirstCommonNode(pHead1, pHead2)
{
// write code here
if(pHead1 === null || pHead2 === null) return null;
const fast = pHead2;
while(pHead1){
while(pHead2){
if(pHead1 === pHead2) return pHead1;
pHead2 = pHead2.next;
}
pHead1 = pHead1.next;
pHead2 = fast;
}
} 快慢指针 原理：这里的pHead1使用慢指针，hHead2使用快指针，当快指针追上慢指针的时候就是公共节点。
发表于 2023-02-11 22:36:24
回复(0)
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2) {
// write code here
let p1 = pHead1
let p2 = pHead2
if (p1 == null || p2 == null) {
return null
}
while (true) {
p1.flag = true
if (p1.next == null) {
break
}
p1 = p1.next
}
while (true) {
if (p2.flag === true) {
return p2
}
if (p2.next == null) {
break
}
p2 = p2.next
}
return null
}
module.exports = {
FindFirstCommonNode: FindFirstCommonNode
};
暴力解法
走过的地方标记一下
发表于 2022-09-10 16:33:15
回复(0)
function FindFirstCommonNode(pHead1, pHead2)
{
// write code here
if(pHead1 == null || pHead2 == null) return null;
var temp1 = pHead1;
var temp2 = pHead2;
var length2 = 0;
var length1 = 0;
while(temp1 !== null){
temp1 = temp1.next;
length1++;
}
while(temp2 !== null){
temp2 = temp2.next;
length2++;
}
if(length1 >= length2){
for(let i = 0; i < length1-length2; i++){
pHead1 = pHead1.next;
}
}else{
for(let i = 0; i < length2-length1; i++){
pHead2 = pHead2.next;
}
}
while(pHead1 !== null && pHead2 !== null){
if(pHead1 == pHead2){
return pHead1;
}
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
return null;
}
{
// write code here
if(pHead1 == null || pHead2 == null) return null;
var temp1 = pHead1;
var temp2 = pHead2;
var length2 = 0;
var length1 = 0;
while(temp1 !== null){
temp1 = temp1.next;
length1++;
}
while(temp2 !== null){
temp2 = temp2.next;
length2++;
}
if(length1 >= length2){
for(let i = 0; i < length1-length2; i++){
pHead1 = pHead1.next;
}
}else{
for(let i = 0; i < length2-length1; i++){
pHead2 = pHead2.next;
}
}
while(pHead1 !== null && pHead2 !== null){
if(pHead1 == pHead2){
return pHead1;
}
pHead1 = pHead1.next;
pHead2 = pHead2.next;
}
return null;
}
发表于 2022-04-19 20:47:01
回复(0)
简洁的JavaScript (参考的高赞Java回答, 这方法是真的聪明!):
function FindFirstCommonNode(pHead1, pHead2)
{
// write code here
if (pHead1 == null || pHead2 == null) return null;
let p1 = pHead1;
let p2 = pHead2;
while (p1 !== p2){
p1 = p1.next;
p2 = p2.next;
if (p1 === p2) break;
if (p1 === null) p1 = pHead2;
if (p2 === null) p2 = pHead1;
}
return p1;
}
发表于 2021-10-09 03:17:28
回复(4)
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
if(!pHead1 || !pHead2) return null
// 获取第一个链表的长度
let len1 = getLength(pHead1)
// 获取第二个链表的长度
let len2 = getLength(pHead2)
// 比较两个链表的长度，长的链表先走
if(len1 >= len2){
let len = len1 - len2
while(len > 0){
pHead1 = pHead1.next
len--
}
}
// 比较两个链表的长度，长的链表先走
else if(len2 >= len1){
let len = len2 - len1
while(len > 0){
pHead2 = pHead2.next
len--
}
}
// 此时链表1跟链表2到尾部的距离一样，齐头并进找到并返回公共结点，找不到返回null
while(pHead1 != pHead2){
pHead1 = pHead1.next
pHead2 = pHead2.next
}
return pHead1
}
// 获取链表长度
function getLength(head){
let len = 0
while(head){
head = head.next
len++
}
return len
}
module.exports = {
FindFirstCommonNode : FindFirstCommonNode
};
this.val = x;
this.next = null;
}*/
function FindFirstCommonNode(pHead1, pHead2)
{
if(!pHead1 || !pHead2) return null
// 获取第一个链表的长度
let len1 = getLength(pHead1)
// 获取第二个链表的长度
let len2 = getLength(pHead2)
// 比较两个链表的长度，长的链表先走
if(len1 >= len2){
let len = len1 - len2
while(len > 0){
pHead1 = pHead1.next
len--
}
}
// 比较两个链表的长度，长的链表先走
else if(len2 >= len1){
let len = len2 - len1
while(len > 0){
pHead2 = pHead2.next
len--
}
}
// 此时链表1跟链表2到尾部的距离一样，齐头并进找到并返回公共结点，找不到返回null
while(pHead1 != pHead2){
pHead1 = pHead1.next
pHead2 = pHead2.next
}
return pHead1
}
// 获取链表长度
function getLength(head){
let len = 0
while(head){
head = head.next
len++
}
return len
}
module.exports = {
FindFirstCommonNode : FindFirstCommonNode
};
发表于 2021-10-01 15:37:56
回复(0)
问题信息
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：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; } };