推荐

完整《剑指Offer》算法题解析系列请点击 👉 《剑指Offer》全解析 Java 版

题目描述

输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
public class Solution {
   
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
   
 
    }
}

思路：

链表 A 的长度为 a ；

链表 b 的长度为 b；

a + b = b + a;

我们用两个指针，

一个先访问A，遍历到A的尾部之后，再从B的首部开始遍历B.

一个先访问A，遍历到B的尾部之后，再从A的首部开始遍历A.

如此，两个指针能同时访问到交点。

比如：

链表A ：4 -> 3 -> 2 -> 1

链表B ：5 -> 2 -> 1

指针 1 的遍历到交点的路径是：4 -> 3 -> 2 -> 1 5 -> 2

指针 2 的遍历到交点的路径是：5 -> 2 -> 1 4 -> 3 -> 2

可以看到，两个指针能同时访问到交点。

实现：

/* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } }*/
public class Solution {
   
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
   
        ListNode L1 = pHead1;
        ListNode L2 = pHead2;
        while (L1 != L2) {
   
            if (L1 == null) {
   
                L1 = pHead2;
            } else {
   
                L1 = L1.next;
            }
            
            if (L2 == null) {
   
                L2 = pHead1;
            } else {
   
                L2 = L2.next;
            }
        } 
        return L1;
    }
}

看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。

这里是猿兄，为你分享程序员的世界。

非常感谢各位大佬们能看到这里，如果觉得文章还不错的话， 求点赞👍 求关注💗 求分享👬求评论📝 这些对猿兄来说真的 非常有用！！！

注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！