首页 > 试题广场 >

两个链表的第一个公共结点

[编程题]两个链表的第一个公共结点
  • 热度指数：689634 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 64M，其他语言128M
  • 算法知识视频讲解
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围：
要求：空间复杂度 ，时间复杂度

例如，输入{1,2,3},{4,5},{6,7}时，两个无环的单向链表的结构如下图所示：

可以看到它们的第一个公共结点的结点值为6，所以返回结点值为6的结点。

输入描述:
输入分为是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，点此查看相关信息
算法知识视频讲解
添加回答
推荐
lizo头像 lizo 
/*
找出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;
    }
};

编辑于 2015-08-18 23:31:25 回复(82)
C
泡泡子_头像 泡泡子_ 
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)
C
牛客183552821号头像 牛客183552821号
    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)
C
一个优雅的程序猿头像 一个优雅的程序猿 
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)
C
想去杭州的高级磨洋工在学习头像 想去杭州的高级磨洋工在学习
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)
C
喜欢划水头像 喜欢划水
// 暴力解法
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)
C
A202302282044461头像 A202302282044461
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)
C
小熊猫的黑眼圈头像 小熊猫的黑眼圈
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)
C
新人波比_头像 新人波比_ 
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)
C
巴尔泽布头像 巴尔泽布
另一种思路：把第一条的链表结尾接上第二条链表的头，如果两链表存在公共节点的话，连接后会出现环状结构，并且环状结构的入口节点就是原本两链表的第一个公共节点。 
/**
 * 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)
C
lijd头像 lijd 
/**
 * 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)
C
厚礼谢头像 厚礼谢
/**
 * 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)
C
80后大叔头像 80后大叔

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)
C
取nm名字全被取了头像 取nm名字全被取了 
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)
C
tao_w头像 tao_w
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)
C
苦闷的伊登offer多多头像 苦闷的伊登offer多多
打卡第三天 
/**
 * 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)
C
Machinist.头像 Machinist. 
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)
C
lmghzzq头像 lmghzzq 
struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode *p=pHead1;
    struct ListNode *q=pHead2;
    int len1=0,len2=0;
    while(p!=NULL){
        len1++;
        p=p->next;
    }
    while(q!=NULL){
        len2++;
        q=q->next;
    }
    if(len1==len2) p=pHead1,q=pHead2;
    if(len1>len2){
        q=pHead2;
        p=pHead1;
        int len=len1-len2;
        for(int i=0;i<len;i++){
            p=p->next;
        }
    }
    if(len1<len2){
        q=pHead2;
        p=pHead1;
        int len=len2-len1;
        for(int i=0;i<len;i++){
            q=q->next;
        }
    }
    while(q!=p){
        p=p->next;
        q=q->next;
    }
    return p;
}

发表于 2022-10-07 20:30:09 回复(0)
提交观点

问题信息

链表
难度：
33条回答 128056浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号