【链表|模拟】相交链表
对于如图所示的两个链表 A、B，标红节点就是我们要找的交点：
如果暂时不考虑题目的约束——函数返回后，链表必须保持原始结构。
我们可以尝试将本题与「环形链表 II」联系起来。
假设两个链表存在公共部分，我们将公共部分的尾节点指向链表 A 的头节点，就可以构造出一个环。
此时，从链表 B 的头节点出发，沿着 B 的独有部分进入环，环的入口恰好就是两个链表的第一个公共节点。因此，我们可以借助「环形链表 II」的思路寻找交点。
不过，这种方法需要修改链表结构，而且还需要额外处理两个链表原本就不相交的情况，因此不适合作为本题的直接解法。
那么，有没有不修改链表结构，也能找到交点的方法呢？
一个可行的方案是交叉遍历。
我们使用两个指针 pA、pB，分别从链表 A、B 的头节点出发，每次各向后移动一个节点。
当某个指针到达 null 时，就让它从另一条链表的头节点重新出发。另一个指针同理。
当 pA == pB 时，遍历结束：
- 如果两个链表相交，两个指针最终会在第一个公共节点处相遇。
- 如果两个链表不相交，两个指针最终都会到达
null。
为什么交叉遍历是正确的？我们来推导一下这一思路背后的数学原理。
设 A 独有部分长度为 $a$，B 独有部分长度为 $b$，公共部分长度为 $c$（不相交时 $c = 0$）。
那么：
- 链表 A 的长度为 $a+c$。
- 链表 B 的长度为 $b+c$。
如果两个链表相交，pA 从 A 的头节点出发，遍历完 A 后切换到 B，最终到达交点，走过的路程为：
$$
(a+c)+b=a+b+c
$$
同理，pB 从 B 的头节点出发，遍历完 B 后切换到 A，最终到达交点，走过的路程为：
$$
(b+c)+a = a + b + c
$$
我们发现，二者到达交点前的路程是一样的：
$$
(a+c)+b = (b+c)+a=a+b+c
$$
这说明，两个指针到达第一个公共节点前，走过的路程相同。由于二者每次都移动一个节点，因此最终会在该节点相遇。
如果两个链表不相交，那么 (c=0)。此时，两个指针分别遍历完 A、B 两条链表，再遍历另一条链表，最终都会到达 null。
由此可见，无论两个链表是否相交，交叉遍历都能保证两个指针最终相遇。
基于这一思路，我们不难写出如下代码：
▼java复制代码public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode p = headA, q = headB; while (p != q) { p = p == null ? headB : p.next; q = q == null ? headA : q.next; } return p; }
