题解 | 链表相交

本题要注意两链表的交点不只是值相等，而且是交点处指针的next域也相等，所以可以理解为交点处指针相同。本题可使用双指针，让指针pa从链表A开始遍历，若遍历完再从链表B开始遍历；让指针pb从链表B开始遍历，若遍历完再遍历链表A，在此过程中pa与pb某一时刻一定会相等。设链表A在到达交点前的长度为len_a，设链表B在到达交点前的长度为len_b，设链表A与B的公共长度为len_c，可以发现指针pa走到交点处的总长度为：len_a+len_c+len_b，指针pb走到交点处的总长度为：len_b+len_c+len_a，二者相等。若走到最后仍未发现交点，最后二指针同时变为空指针nullptr，说明两链表不存在交点。

#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};


ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *pa=headA;
    ListNode *pb=headB;
    while(pa!=pb){
        pa=pa?pa->next:headB;
        pb=pb?pb->next:headA;
    }
    if(pa==nullptr) return nullptr;
    return pa;
}