题解 | #两个链表的第一个公共结点#

/*
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 p1 = pHead1, p2 = pHead2;
        while (p1 != p2) {
            p1 = (p1 != null) ? p1.next : pHead2;
            p2 = (p2 != null) ? p2.next : pHead1;
        }
        return p1;
    }
}

算法思路：

定义两个指针 p1 和 p2，分别指向两个链表的头节点，然后让它们同时遍历两个链表。当 p1 遍历完当前链表时，将 p1 指向另一个链表的头节点，继续遍历；当 p2 遍历完当前链表时，将 p2 指向另一个链表的头节点，继续遍历。当 p1 和 p2 相遇时，即为它们的第一个公共节点。

为什么这个算法可行呢？假设两个链表的长度分别为 a 和 b，它们的公共部分长度为 c，则有以下三种情况：

1. a = b，p1 和 p2 遍历完自己的链表后同时到达链表尾部，即 p1 == p2 == null，此时返回 null。
2. a < b，p1 先到达链表尾部，此时将 p1 指向另一个链表的头节点，即指向长度为 b 的链表的头节点，继续遍历。p2 继续遍历自己的链表，当 p2 到达链表尾部时，将 p2 指向另一个链表的头节点，即指向长度为 a 的链表的头节点，继续遍历。由于 p1 多走了 b - a 步，p2 多走了 a - b 步，因此此时 p1 和 p2 距离公共节点的长度相等，同时移动，必定会在公共节点处相遇。
3. a > b，同 2，只是 p2 先到达链表尾部，p1 后到达，然后继续遍历，最终也会在公共节点处相遇。

时间复杂度分析：

整个算法只需要遍历每个链表一次，时间复杂度是 O(n)。

空间复杂度分析：

只需要使用常数个额外的指针变量，空间复杂度是 O(1)。