一、题目

输入两个链表，找出它们的第一个公共节点。

二、示例

如下面的两个链表：

在节点 c1 开始相交。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

三、解题思路

关于这道题，其实看似题目描述得很简单，但是实际代码实现起来，还是会比较绕的。首先，这里所谓的公共节点，是相同的节点实例对象，而并非val值相同。其次是，程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。那么我们来分析一下两个指针分别从两条链表的头部开始遍历的路径是怎么样的？下面以两种情况进行分析：

3.1> 情况1：存在共同节点

我们创建两个指针p1和p2，分别指向第1条链表的头节点和第2条链表的头节点。然后同时向后遍历，并且在遍历过程中进行节点的对比，如果p1==p2（不为null），则说明找到了共同的节点。

那么我们遍历的路径如下：

【指针p1】先遍历第1条链表，如果没有找到共同节点，再继续遍历第2条链表。
【指针p2】先遍历第2条链表，如果没有找到共同节点，再继续遍历第1条链表。

为什么这样遍历可以遇到共同节点呢？ 我们以下面的图为例，共同的节点是Node(6)；

【指针p1可以到达Node(6)的路径是】A 和 A+C+B；
【指针p2可以到达Node(6)的路径是】B 和 B+C+A；

又因为p1和p2指针是同时向后遍历的，且遍历的“步长”相同，那么就会在A+C+B == B+C+A的路径下相遇。

3.2> 情况2：不存在共同节点

那么下面我们来看一下如果没有共同节点的情况下，怎么判断呢？

我们p1指针遍历完两条链表后经过的节点数量与p2指针遍历完两条链表后经过的节点数量是相同的，因为

【p1经过节点长度是】A+C+B；
【p2经过的节点长度是】B+C+A；

那么，当p1和p2遍历完两条链表后，他们一定是p1==p2==null，所以如果出现这种情况，则表示两条链表没有共同的节点。

上面文字描述如果不容易理解，请见下面的图示，其展示了【情况1】和【情况2】两种情况寻找共同节点的步骤。

四、代码实现

class Solution {
    ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;
        while (p1 != p2) {
            p1 = p1 != null ? p1.next : headB; 
            p2 = p2 != null ? p2.next : headA;
        }
        return p1;
    }
}