双指针,不计算链表长度
设置指向headA和headB的指针pa、pb,分别遍历两个链表,每次循环同时更新pa和pb。
- 当链表A遍历完之后,即pa为空时,将pa指向headB;
- 当链表B遍历完之后,即pa为空时,将pb指向headA;
- 当pa与pb相等时,即指向同一个节点,该节点即为相交起始节点。
- 若链表不相交,则pa、pb同时为空时退出循环,即如果链表不相交,pa与pb在遍历过全部节点后同时指向结尾空节点,此时退出循环,返回空。
证明思路
设链表A不相交部分长度为a,链表B不相交部分长度为b,两个链表相交部分长度为c。
在pa指向链表A时,即pa为空之前,pa经过链表A不相交部分和相交部分,走过的长度为a+c;
pa指向链表B后,在移动相交节点之前经过链表B不相交部分,走过的长度为b,总合为a+c+b。
同理,pb走过长度的总合为b+c+a。二者相等,即pa与pb可同时到达相交起始节点。
该方法可避免计算具体链表长度。
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
//链表为空时,返回空指针
if(headA == nullptr || headB == nullptr) return nullptr;
ListNode* pa = headA;
ListNode* pb = headB;
//pa与pb在遍历过全部节点后,同时指向结尾空节点时退出循环
while(pa != nullptr || pb != nullptr){
//pa为空时,将pa指向headB
if(pa == nullptr){
pa = headB;
}
//pa为空时,将pb指向headA
if(pb == nullptr){
pb = headA;
}
//pa与pb相等时,返回相交起始节点
if(pa == pb){
return pa;
}
pa = pa->next;
pb = pb->next;
}
return nullptr;
}
};