Leetcode algorithm The first common node of two linked lists

Topic link ： The finger of the sword Offer 52. The first common node of two linked lists

Ideas

Algorithm ： Double pointer + mathematics
data structure ： Linked list
Ideas ： I remember talking about this problem in the elementary class of Zuoshen algorithm , A little forgotten , The way to do this is to move both hands forward , If pa At the end, move to pb, If pb At the end, move to pa, I'm sure to meet you in the end , But the proof of why we met is a little forgotten . The algorithm I provide here is two pointers plus a little math .

---

First consider the boundary case , If one of the two pointers is null , Then there must be no intersecting nodes , direct return nullptr Just OK 了 .
Then you need to calculate the length of the two linked lists lenA and lenB And the length difference diff, Then we need to redefine , Give Way A Represents a long linked list ,B Indicates a short linked list .
If two linked lists have intersecting parts , So the long piece must be in the disjoint part , Because after the conversion A A long , So the point to A The pointer of can go first diff Step , Then the two pointers go together , If it's equal , It means that the first intersection node is found , Otherwise, it means that the two linked lists have no intersecting parts .

Code

C++

class Solution {
    
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    
        if (headA == nullptr || headB == nullptr) {
    
            return nullptr;
        }
        int lenA = 0, lenB = 0;
        ListNode *pA = headA, *pB = headB;
        while (pA != nullptr) {
    
            lenA++;
            pA = pA->next;
        }
        while (pB != nullptr) {
    
            lenB++;
            pB = pB->next;
        }
        int diff = abs(lenA - lenB);
        //  If linked list B Is longer than the linked list A The length of , In exchange for A、B
        if (lenB > lenA) {
    
            pA = headA;
            headA = headB;
            headB = pA;
        }
        // headA Go ahead diff Step 
        for (int i = 0; i < diff; i++) {
    
            headA = headA->next;
        }
        while (headA != nullptr) {
    
            if (headA == headB) {
    
                return headA;
            } else {
    
                headA = headA->next;
                headB = headB->next;
            }
        }
        return nullptr;
    }
};