题目
解题思路
快慢指针（错的人迟早会走散，而对的人迟早会相逢！浪漫解法~）
-
创建两个指针
pA和pB，分别初始化为链表A和B的头结点。然后让它们向后逐结点遍历。 -
当
pA到达链表的尾部时，将它重定位到链表B的头结点 (你没看错，就是链表B); 类似的，当pB到达链表的尾部时，将它重定位到链表A的头结点。 -
若在某一时刻
pA和pB相遇，则pA/pB为相交结点。 -
想弄清楚为什么这样可行, 可以考虑以下两个链表:
A={1,3,5,7,9,11}和B={2,4,9,11}，相交于结点9。 由于B.length (4) < A.length (6)，pB比pA少经过 2 个结点，会先到达尾部。将pB重定向到pA的头结点，pA重定向到pB的头结点后，pB要比pA多走2个结点。因此，它们会同时到达交点。 -
如果两个链表存在相交，它们末尾的结点必然相同。因此当
pA/pB到达链表结尾时，记录下链表pA/pB对应的元素。若最后元素不相同，则两个链表不相交。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == NULL || headB == NULL) return NULL;
ListNode *headA_H = headA, *headB_H = headB;
ListNode *headA_E = NULL, *headB_E = NULL;
while (true) {
if (headA == headB) return headA;
if (headA_E != NULL && headB_E != NULL && headA_E != headB_E) return NULL;
if (headA->next != NULL)
headA = headA->next;
else {
headA_E = headA;
headA = headB_H;
}
if (headB->next != NULL)
headB = headB->next;
else {
headB_E = headB;
headB = headA_H;
}
}
return NULL;
}
};
