相交链表 | LeetCode 160
内容提要
LeetCode 160 相交链表要求找出两个单链表的首个公共节点，无交点返回 null，且不得改变链表结构。解法采用双指针：p1 遍历完 A 后转去遍历 B，p2 遍历完 B 后转去遍历 A，使两指针同步到达交点。时间复杂度 O(m+n)，空间复杂度 O(1)。
延伸解读
双指针切换的核心逻辑
文章指出，直接让两个指针分别在两条链表上前进，无法同时到达公共节点。解法是让 p1 遍历完 A 后转去遍历 B，p2 遍历完 B 后转去遍历 A，相当于在逻辑上把两条链表拼接起来。这样两个指针走过的总长度相同，因此会同时进入公共部分并到达首个相交节点。理解这一“逻辑拼接”是掌握该解法的关键。
复杂度与实现约束
该解法的时间复杂度为 O(m+n)，因为每个指针各遍历两条链表一次；空间复杂度为 O(1)，只使用了两个指针。题目还要求函数返回结果后链表必须保持原始结构，因此不能通过修改 next 指针来标记节点。双指针切换只改变指针的遍历路径，不改变链表本身，符合这一约束。
评测输入与无交点情形
评测系统通过 intersectVal、listA、listB、skipA、skipB 构造链表，其中 intersectVal 为 0 表示无交点。若两链表无交点，双指针在各自遍历完两条链表后都会变为 null，从而返回 null。这一情形不需要额外分支处理，说明该解法对有无交点具有统一性。
Q&A
LeetCode 160 相交链表题目的要求是什么？
给定两个单链表的头节点 headA 和 headB，找出并返回两个单链表相交的起始节点；如果不存在相交节点，则返回 null。题目保证整个链式结构中不存在环，且函数返回结果后链表必须保持原始结构。
如何用双指针法找到两个链表的相交节点？
使用两个指针 p1 和 p2 分别从 headA 和 headB 出发。p1 遍历完链表 A 后转去遍历链表 B，p2 遍历完链表 B 后转去遍历链表 A。这样两个指针会同时到达相交节点；若没有交点，则最终同时变为 null。
双指针法为什么能让两个指针同时到达相交节点？
因为让 p1 遍历完 A 后接着遍历 B，p2 遍历完 B 后接着遍历 A，相当于在逻辑上将两条链表拼接在一起。这样两个指针走过的总路径长度相同，因此会同时进入公共部分，从而同时到达相交节点。
相交链表问题的时间复杂度和空间复杂度是多少？
时间复杂度为 O(m+n)，其中 m 和 n 分别是链表 headA 和 headB 的长度，两个指针同时遍历两个链表，每个指针遍历两个链表各一次。空间复杂度为 O(1)，只使用了两个指针。
如果两个链表没有交点，双指针法会返回什么？
如果两个链表没有交点，两个指针最终会同时遍历完两条链表并变为 null，此时返回 null，符合题目要求。
解题时对链表结构有什么限制？
题目要求函数返回结果后，链表必须保持其原始结构，即不能修改链表节点的指向或值。
