【算法面试必刷Java版十】两个链表的第一个公共结点

盲目刷题，浪费大量时间，博主这里推荐一个面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101

🏄🏻作者简介：CSDN博客专家，华为云云享专家，阿里云专家博主，疯狂coding的普通码农一枚

    

🚴🏻‍♂️个人主页：莫逸风

    

👨🏻‍💻专栏题目地址👉🏻牛客网面试必刷TOP101👈🏻

    

🇨🇳喜欢文章欢迎大家👍🏻点赞🙏🏻关注⭐️收藏📄评论↗️转发

题目：两个链表的第一个公共结点

描述：

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

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

思路：双指针

使用两个指针n1,n2，分别指向两个链表的头部。

当一个指针走到链表末尾，则将他指向另一个链表的头部，如果他们有公共节点，则他们一定会在非初始链表遍历时相遇。

因为两个指针，同样的速度，走完同样长度（链表1+链表2），不管两条链表有无相同节点，都能够到达同时到达终点。

代码：

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
    if (pHead1 == pHead2){
        return pHead1;
    }
    ListNode cur1 = pHead1;
    ListNode cur2 = pHead2;
    int flag1 = 0;
    int flag2 = 0;
    while (flag1 + flag2 < 3) {
        if (cur1 == null) {
            cur1 = pHead2;
            flag1 = flag1 + 1;
        }else {
            cur1 = cur1.next;
        }
        if (cur2 == null) {
            cur2 = pHead1;
            flag2 = flag2 + 1;
        }else {
            cur2 = cur2.next;
        }
        if (cur1 == cur2) {
            return cur1;
        }
    }
    return null;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

推荐牛客网面试必刷算法题库，刷完足够面试了。传送门：牛客网面试必刷TOP101