首页 > 试题广场 >

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

[编程题]两个链表的第一个公共结点

热度指数：709512 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围： $n \le 1000$
要求：空间复杂度 $O(1)$ ，时间复杂度 $O(n)$

例如，输入{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

/*
找出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)

Java

人间水长东

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) {
        // 左程云老师讲过这道题。分别测量两条链表的长度length1和length2，计算二者的差值diff
        // 先让较长链表走diff个结点，然后二者同时一次走一个结点，相遇的结点就是第一个公共节点

        // 算法的时间复杂度O(N)，额外空间复杂度O(1)

        // 1.分别遍历一遍链表，得到总共有几个结点
        if (pHead1 == null) {
            return null;
        }
        if (pHead2 == null) {
            return null;
        }
        // 确保两个链表都至少有一个结点
        int length1 = 0;
        int length2 = 0;
        ListNode cur = pHead1;
        while (cur != null) {
            length1++;
            cur = cur.next;
        }
        cur = pHead2;
        while (cur != null) {
            length2++;
            cur = cur.next;
        }

        // 2.找到较长的链表并计算差值
        ListNode longListHead = length1 >= length2 ? pHead1 : pHead2;
        ListNode shortListHead = length1 >= length2 ? pHead2 : pHead1;
        int diff = Math.abs(length1 - length2);

        // 3.先让较长链表走diff个结点，然后二者同时一次走一个结点，相遇的结点就是第一个公共节点
        ListNode longListCur = longListHead;
        ListNode shortListCur = shortListHead;
        while(diff > 0) {
            longListCur = longListCur.next;
            diff--;
        }
        // 4.此时，令longListCur和shortListCur同时一次往前走一个结点，直到它们相遇
        while (longListCur != shortListCur) {
            longListCur = longListCur.next;
            shortListCur = shortListCur.next;
        }
        // 5.返回相遇的结点，就是第一个公共结点
        return longListCur;
    }
}

发表于 2024-07-26 23:13:23 回复(0)

Java

牛客784614878号

public class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        //先保留两个头结点
        ListNode p1 = pHead1;
        ListNode p2 = pHead2;
        while (pHead1 != pHead2) {
            if (pHead1 == null) { //遍历到了尾部,遍历另一个链表
                pHead1 = p2;
            } else {
                pHead1 = pHead1.next;
            }
            if (pHead2 == null) { //遍历到了尾部，遍历另一个链表
                pHead2 = p1;
            } else {
                pHead2 = pHead2.next;
            }
        }
        return pHead1;
    }
}

发表于 2024-07-19 15:43:23 回复(0)

Java

面向对象的修勾很机智

public class Solution {

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

HashSet<ListNode> hashSet = new HashSet<>();

ListNode h1 = pHead1;

while(h1!=null){

hashSet.add(h1);

h1=h1.next;

}

while(pHead2!=null){

if(hashSet.contains(pHead2)){

return pHead2;

}

pHead2=pHead2.next;

}

return null;

}

发表于 2024-07-17 19:30:02 回复(0)

Java

在爱_的回归线

求教！！！

采用两层while循环分别遍历两个链表，当内层遍历的节点等于外层的节点时，break，最后通过临时变量temp返回。代码提交，结果8/9，错了最后一个，想不明白，官方示例也看不全！求佬告知！

public class Solution {

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

ListNode temp = null;

ListNode cur = pHead2;

while (pHead1 != null) {

while (cur != null) {

if (cur.val == pHead1.val) {

temp = cur;

break;

}

cur = cur.next;

}

if (temp == pHead1) {

break;

} else {

cur = pHead2;

pHead1 = pHead1.next;

}

return temp;

}

发表于 2024-07-03 16:30:27 回复(0)

Java

微笑向日葵

按理来说set存储是不满足空间复杂度要求的，可是毕竟能过、、但是大佬给出遍历两个链表、一定会相遇这个方法哪怕有动图我也想不通、、好挫败

发表于 2024-04-28 19:39:46 回复(0)

Java

牛客119190309号

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)

Java

阿mini默

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)

Java

快乐仕忆

题目看了半天，尝试了两次才看懂。题目关键要表达的是两个链表最后一部分要么全部相等，要么不相等。我理解成了找到一个相等的节点。

发表于 2023-12-05 22:33:34 回复(0)

Java

-Panda君-

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)

Java

盛夏光年20171125222943

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)

Java

牛客276339250号

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)

Java

夹仲见歌

用哈希做了一下又看了官方题解，有一个小问题请教一下，用这种方法如果两个链表没有公共部分会进入无限循环吗？

public class Solution {
    public ListNode FindFirstCommonNode(ListNode p1, ListNode p2) {
        ListNode r1=p1,r2 = p2;
        while(r1!=r2){
            r1 = (r1==null)?p2:r1.next;
            r2 = (r2==null)?p1:r2.next;
        }
        return r1;
    }
}

发表于 2023-09-17 14:52:39 回复(0)

Java

你一定会有offer

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)

Java

北极的小神龙

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)

Java

做则必成的勇气和信心

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)

Java

抓住努力的尾巴

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)

Java

华王135608

两种，一种 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)

Java

小咖啡

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)

Java

牛客725140028号

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)

Java

牛客884959935号

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)

提交观点

问题信息

链表

难度：

237条回答 2555收藏 129579浏览

通过挑战的用户

查看代码

少糖加蛋娃哈哈

2023-03-14 10:58:05
牛客20133...

2023-03-10 16:30:41
牛客17038...

2023-03-09 17:20:34
K乀

2023-02-27 22:56:47
GeekExp...

2023-02-16 14:00:55

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

输入描述:

输出描述:

输入

输出

说明

输入

输出

说明

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题