在刷 LeetCode 链表题的过程中，有一道非常经典的题目——相交链表（Intersection of Two Linked Lists）。今天我们来聊聊这道题目的解法和思想。
题目描述
给你两个单链表 headA 和 headB，请你找出并返回它们的第一个公共节点。如果两个链表没有交点，返回 null 即可。
⚠️ 注意：题目中所说的「相交」，指的是节点地址相同，而非节点值相同。
思路分析
最直观的做法是暴力遍历或用哈希表记录，但我们今天要介绍的是一种更加优雅的做法：双指针法。
解法精髓：双指针
我们用两个指针 A 和 B 分别遍历链表 headA 和 headB：
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode A = headA;ListNode B = headB;while (A != B) {A = A != null ? A.next : headB;B = B != null ? B.next : headA;}return A;}
}
思维过程详解
-
两个指针开始分别走各自的链表；
-
当其中一个到达链表尾部时，跳到另一个链表的头部继续走；
-
如果两个链表有交点，最终它们会在交点相遇；
-
如果没有交点，两个指针都会在走完
A + B长度之后同时为null，跳出循环。
这种方式其实是用时间换空间，让两个指针走了相同的路径长度。
举个例子
假设链表如下：
List A: 4 → 1 → 8 → 4 → 5
List B: 5 → 0 → 1 → 8 → 4 → 5
两个链表在节点值为 8 的位置相交（当然我们比较的是节点地址）。
-
A指针走完4 → 1 → 8 → 4 → 5，然后跳到headB； -
B指针走完5 → 0 → 1 → 8 → 4 → 5，然后跳到headA； -
最终它们在节点
8处相遇。
复杂度分析
-
时间复杂度：O(m + n)，m 和 n 分别为两个链表的长度；
-
空间复杂度：O(1)，只用了两个指针，无需额外空间。