 最优解))
LeetCode 160. 相交链表
📌 题目描述
题目级别：简单
给你两个单链表的头节点headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。
进阶挑战：你能否设计一个时间复杂度O(N)O(N)O(N)、仅用O(1)O(1)O(1)内存的解决方案？
💡 破题思路：走过你走过的路
如果用哈希表（HashSet）存下其中一个链表的所有节点，再去另一个链表里找，虽然能解决，但空间复杂度是O(N)O(N)O(N)，不符合面试官追求极致的胃口。
既然两个链表相交后的尾部是完全一样的，他们之所以不能同时到达相交点，仅仅是因为前面的独立长度不一样。
绝妙的“路程互补”算法：
定义两个指针pA和pB，分别从headA和headB出发。
- 每人每次走一步。
- 当
pA走到底（null）时，让它从headB重新开始走。 - 当
pB走到底（null）时，让它从headA重新开始走。
为什么这样一定行？
假设链表 A 的独立部分长度为aaa，链表 B 的独立部分长度为bbb，相交部分长度为ccc。
pA走过的路程：a+c+ba + c + ba+c+bpB走过的路程：b+c+ab + c + ab+c+a
两人走过的总长度完全一样！所以他们最终一定会同时走到那个相交的起点。
如果根本不相交（c=0c=0c=0），那他们俩就会在走了a+ba+ba+b步之后，双双变成null并在虚无中相遇，代码同样完美成立。
💻 C++ 代码实现 (极简双指针法)
classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){// 如果有任何一个链表为空，绝不可能相交if(!headA||!headB)returnnullptr;ListNode*pA=headA;ListNode*pB=headB;// 只要两人没相遇，就一直走while(pA!=pB){// pA 走完了，就跳到 B 链表头；否则继续走pA=pA==nullptr?headB:pA->next;// pB 走完了，就跳到 A 链表头；否则继续走pB=pB==nullptr?headA:pB->next;}// 相遇点就是相交节点（如果不相交，这里正好返回 nullptr）returnpA;}};
