输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
数据范围： 
要求：空间复杂度)
，时间复杂度 )
要求：空间复杂度
例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：
可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。
[编程题]两个链表的第一个公共结点
- 热度指数：709512 时间限制：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，点此查看相关信息
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
*
* @param pHead1 ListNode类
* @param pHead2 ListNode类
* @return ListNode类
*/
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1,
struct ListNode* pHead2 ) {
// write code here
struct ListNode* temp;
if (pHead1 == NULL || pHead2 == NULL) {
return NULL;
}
while (pHead1 != NULL) {
temp = pHead2;
while (temp != NULL) {
if (temp == pHead1) {
return temp;
}
temp = temp->next;
}
pHead1 = pHead1->next;
}
return NULL;
}
发表于 2024-07-13 22:19:24
回复(0)
struct ListNode* henFindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
if (!pHead1) {
return NULL;
}
if (!pHead2) {
return NULL;
}
struct ListNode*p1=pHead1;
struct ListNode*p2=pHead2;
int n1=0;
int n2=0;
while (p1!=NULL) {
p1=p1->next;
n1++;
}
p1=pHead1;
while (p2!=NULL) {
p2=p2->next;
n2++;
}
p2=pHead2;
if (n1>n2) {
for (int i=0;i<n1-n2; i++) {
p1=p1->next;
}
}
if (n1<n2) {
for (int i=0;i<n2-n1; i++) {
p2=p2->next;
}
}
while (p1!=p2) {
p1=p1->next;
p2=p2->next;
}
return p1;
} 使输入的两个链表的尾部对齐
编辑于 2024-04-11 18:16:25
回复(0)
if((pHead1==NULL)||(pHead2==NULL))
return NULL;
struct ListNode *iop[1000];
struct ListNode *pd1=pHead1,*pd2=pHead2;
int iopp=0;
while (pd1!=NULL) {
iop[iopp]=pd1;
pd1=pd1->next;
pd2=pHead2;
while(pd2!=NULL)
{
if(iop[iopp]==pd2)
return iop[iopp];
pd2=pd2->next;
}
iopp++;
}
// write code here
return NULL;
编辑于 2024-03-23 10:56:02
回复(0)
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
struct ListNode *p1, *p2 = pHead2;
if(pHead1==NULL || pHead2==NULL)
return NULL;
while(p2!=NULL) {
p1 = pHead1;
while(p1!=NULL) {
if(p1==p2)
return p1;
p1 = p1->next;
}
p2 = p2->next;
}
return NULL;
}
编辑于 2024-03-15 14:13:21
回复(0)
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
struct ListNode* head1=pHead1;
struct ListNode* head2=pHead2;
int len1=0;
int len2=0;
if(pHead1==NULL)
{
return NULL;
}
if(pHead2==NULL)
{
return NULL;
}
while(head1->next)
{
len1++;
head1=head1->next;
}
while(head2->next)
{
len2++;
head2=head2->next;
}
if(head2!=head1)
{
return NULL;
}
if(len1>=len2)
{
while(len1-len2)
{
pHead1=pHead1->next;
len1--;
}
}
else {
while(len2-len1)
{
pHead2=pHead2->next;
len2--;
}
}
while(pHead1&&pHead2)
{
if(pHead1==pHead2)
{
return pHead1;
}
pHead1=pHead1->next;
pHead2=pHead2->next;
}
return NULL;
}
编辑于 2024-03-02 09:57:06
回复(1)
// 暴力解法
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
// write code here
if (pHead1 == NULL || pHead2 == NULL ) {
return NULL;
}
struct ListNode *p1 = pHead1;
struct ListNode *p2 = pHead2;
struct ListNode *ret = (struct ListNode *)malloc(sizeof (struct ListNode ));
while (p1 != NULL) {
while (p2) {
if (p2 == p1) {
ret = p2;
return ret;
}
p2 = p2->next;
}
p2 = pHead2;
p1 = p1->next;
}
return NULL;
}
发表于 2023-11-28 09:26:16
回复(0)
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
// write code here
struct ListNode * p1 = pHead1;
struct ListNode * p2 = pHead2;
int l1=0, l2=0;
while (p1) {
l1++;
p1 = p1->next;
}
while (p2) {
l2++;
p2 = p2->next;
}
int sub = l1 > l2 ? l1 - l2 : l2 - l1;
p1 = pHead1;
p2 = pHead2;
if (l1>l2) {
while (sub--) {
p1 = p1->next;
}
}
else if(l1<l2) {
while (sub--) {
p2 = p2->next;
}
}
while (p1!=p2) {
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
发表于 2023-09-04 16:38:09
回复(0)
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 )
{
// write code here
struct ListNode*end=pHead2;
struct ListNode*fast=pHead1;
struct ListNode*slow=pHead1;
struct ListNode*p=pHead1;
if(pHead1&&pHead2)
{
while(end->next)
{
end=end->next;
}
end->next=pHead2;
do
{
slow=slow->next;
fast=fast->next->next;
if(!slow||!fast)
{
return NULL;
}
}while(slow!=fast);
while(p!=fast)
{
p=p->next;
fast=fast->next;
}
end->next=NULL;
return p;
}
return NULL;
}
发表于 2023-07-03 22:40:34
回复(0)
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
// write code here
//1\第一个的尾连接到第二个的头，是环状则返回值，不是环状就返回空
//2\两个指针分别走两个链表
struct ListNode* n1 = pHead1;
struct ListNode* n2 = pHead2;
int cnt = 0;
for(n1=pHead1;n1!=NULL&&cnt<1000;n1=n1->next)
{
for(n2=pHead2;n2!=NULL&&cnt<1000;n2=n2->next)
{
if(n1 == n2)
{
return n1;
}
}
}
return NULL;
}
发表于 2023-04-03 10:45:16
回复(0)
另一种思路：把第一条的链表结尾接上第二条链表的头，如果两链表存在公共节点的话，连接后会出现环状结构，并且环状结构的入口节点就是原本两链表的第一个公共节点。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
* @param pHead1 ListNode类
* @param pHead2 ListNode类
* @return ListNode类
*/
struct ListNode* EntryNodeOfLoop(struct ListNode* pHead ) {
// write code here
struct ListNode* slow = pHead;
struct ListNode* fast = pHead;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast) break;
}
if (!fast || !fast->next) return NULL;
else {
slow = pHead;
while (slow != fast) {
slow = slow->next;
fast = fast->next;
}
return slow;
};
}
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1,struct ListNode* pHead2 ) {
struct ListNode* p1 = pHead1;
struct ListNode* p2 = pHead2;
struct ListNode* tail = p1;
if (!p1 || !p2) return NULL;
else if (p1 == p2) return p1;
else {
while (tail->next) tail=tail->next;
tail->next = p2;
p2 = EntryNodeOfLoop(p1);
if(!p2){
tail->next = NULL;
return NULL;
}else {
tail->next = NULL;
return p2;
}
}
}
发表于 2023-02-05 13:09:51
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
*
* @param pHead1 ListNode类
* @param pHead2 ListNode类
* @return ListNode类
*/
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
// write code here
if (pHead1 == NULL || pHead2 == NULL) {
return NULL;
}
struct ListNode* ptr1 = pHead1, *ptr2 = pHead2;
while (ptr1) {
ptr2 = pHead2;
while (ptr2) {
if (ptr1 == ptr2) {
return ptr1;
}else {
ptr2 = ptr2->next;
}
}
ptr1 = ptr1->next;
}
return NULL;
}
发表于 2023-01-17 08:01:48
回复(0)
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
*
* @param pHead1 ListNode类
* @param pHead2 ListNode类
* @return ListNode类
*/
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
// write code here
int num1 = 0;
int num2 = 0;
struct ListNode *p1 = pHead1;
struct ListNode *p2 = pHead2;
while(p1)
{
num1++;
p1 = p1->next;
}
while(p2)
{
num2++;
p2 = p2->next;
}
p1 = pHead1;
p2 = pHead2;
int num = num1 - num2;
if(num > 0)
{
for(int i = 0; i < num; i++)
{
p1 = p1->next;
}
}
else
{
for(int i = 0; i < -num; i++)
{
p2 = p2->next;
}
}
while(p1 && p2)
{
if(p1->next == p2->next)
break;
p1 = p1->next;
p2 = p2->next;
}
if(p1 == NULL || p2 == NULL)
return NULL;
if(p1 == p2)
return p1;
return p1->next;
return NULL;
}
发表于 2022-11-12 21:01:22
回复(0)
2个指针同时把2个链表都跑一遍，这个想法太秒了
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
// write code here
struct ListNode* p = pHead1;
struct ListNode* q = pHead2;
while(p!=NULL || q!=NULL) {
if(p!=NULL&&q!=NULL&&p->val==q->val) break;
if(p==NULL) p=pHead2;
else p=p->next;
if(q==NULL) q=pHead1;
else q=q->next;
}
return p;
}
发表于 2022-11-12 11:15:57
回复(1)
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 )
{
struct ListNode *p1 = pHead1;
struct ListNode *p2 = pHead2;
while(p1!=p2){
p1 = (p1==NULL ? pHead2 : p1->next);
p2 = (p2==NULL ? pHead1 : p2->next);
}
return p1;
// write code here
}
发表于 2022-11-02 21:16:03
回复(0)
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
if(pHead1==NULL||pHead2==NULL)
{
return NULL;
}
int len1=1;
int len2=1;
struct ListNode* cur1=pHead1,* cur2=pHead2;
while(cur1->next)
{
++len1;
cur1=cur1->next;
}
while(cur2->next)
{
++len2;
cur2=cur2->next;
}
if(cur1!=cur2)
{
return NULL;
}
int sub=abs(len1-len2);
struct ListNode* longlist=pHead1;
struct ListNode* shortlist=pHead2;
if(len1<len2)
{
longlist=pHead2;
shortlist=pHead1;
}
while(sub--)
{
longlist=longlist->next;
}
while(longlist!=shortlist)
{
longlist=longlist->next;
shortlist=shortlist->next;
}
return shortlist;
}
发表于 2022-10-29 09:51:37
回复(0)
打卡第三天
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
/**
*
* @param pHead1 ListNode类
* @param pHead2 ListNode类
* @return ListNode类
*/
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1,
struct ListNode* pHead2 ) {
// write code here
struct ListNode* p1 = pHead1, *p2 = pHead2;
if (pHead1 == NULL || pHead2 == NULL) return NULL;
while (p1 != p2) {
p1 = p1->next;
p2 = p2->next;
if (p1 != p2) {//这一步非常重要 都到表尾NULL也相等
if (p1 == NULL) {
p1 = pHead2;
}
if (p2 == NULL) {
p2 = pHead1;
}
}
}
return p1;
}
发表于 2022-10-27 19:40:11
回复(0)
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 )
{
//若一个链表为空，则没有公共结点
if (pHead1 == NULL || pHead2 == NULL)
{
return NULL;
}
int count1 = 0, count2 = 0;
struct ListNode* cur1 = pHead1, *cur2 = pHead2;
//计算链表1的结点个数
while (cur1)
{
count1++;
cur1 = cur1->next;
}
//计算链表2的结点个数
while (cur2)
{
count2++;
cur2 = cur2->next;
}
cur1 = pHead1;
cur2 = pHead2;
int dif = count1 - count2; //计算差值
if (dif > 0) //链表1长，所以链表1的指针要先走dif步
{
while (dif--)
{
cur1 = cur1->next;
}
}
else if (dif < 0) //链表2长，所以链表2的指针要先走ABS(dif)步
{
while (dif++)
{
cur2 = cur2->next;
}
}
//此时2个链表长度相等，指针一起走
while (cur1)
{
if (cur1 == cur2 && cur1 != NULL)
{
return cur1; //找到了第一个公共结点
}
cur1 = cur1->next;
cur2 = cur2->next;
}
return NULL; //未找到
} 核心思想：两个链表的长度差
发表于 2022-10-26 11:26:12
回复(0)
问题信息
难度：
34条回答
2555收藏
129580浏览
通过挑战的用户
查看代码-
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; } };