【Hot 100 刷题计划】 LeetCode 160. 相交链表 | C++ 浪漫双指针 (空间 O(1) 最优解)

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走过的路程acba c bacbpB走过的路程bcab c abca两人走过的总长度完全一样所以他们最终一定会同时走到那个相交的起点。如果根本不相交c0c0c0那他们俩就会在走了ababab步之后双双变成null并在虚无中相遇代码同样完美成立。 C 代码实现 (极简双指针法)classSolution{public:ListNode*getIntersectionNode(ListNode*headA,ListNode*headB){// 如果有任何一个链表为空绝不可能相交if(!headA||!headB)returnnullptr;ListNode*pAheadA;ListNode*pBheadB;// 只要两人没相遇就一直走while(pA!pB){// pA 走完了就跳到 B 链表头否则继续走pApAnullptr?headB:pA-next;// pB 走完了就跳到 A 链表头否则继续走pBpBnullptr?headA:pB-next;}// 相遇点就是相交节点如果不相交这里正好返回 nullptrreturnpA;}};