双指针法快速查找链表的公共节点

题目链接-来源：力扣（LeetCode）

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

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

思路：

考虑 A 链表长度为 a， B 链表长度为 b，两表公共部分长度为 c，（0 <= c <= a, b）。在不知道 a 和 b 的情况下，我们可以确定 a + (b - c) = b + (a - c)。也就是说，我们用一个指针遍历一遍 a 链表，再从 b 链表开始前进，以及用另一个指针遍历一遍 b 链表，再从 a链表开始前进，二者走到公共链表处花费的步数是一样的，尽管我们不知道何处是公共链表。
于是我们只要同时推进两指针，在每次前进时都比较一下二者是否相等（注意，当二者无公共节点时，也就是 c = 0 的情况，我们会遍历到两链表的末尾 null 处，此时依然有二者相等），若相等，中止推进，直接返回相等节点即可。

时间复杂度：O(a + b)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode curA = headA, curB = headB;
        while (curA != curB) {
            if (curA == null) {
                curA = headB;
            } else {
                curA = curA.next;
            }
            if (curB == null) {
                curB = headA;
            } else {
                curB = curB.next;
            }
        }
        return curA;
    }
}