【LeetCode-160 | 链表相交】

1.jpg 2.jpg 3.jpg 4.jpg

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


/*
    解题思路:
        1.指针curA指向A链表，指针curB指向B链表，依次往后遍历
        2.如果curA到了末尾，则curA = headB继续遍历
        3.如果curB到了末尾，则curB = headA继续遍历
        4.当较长链表指针指向较短链表头部节点时，两个链表之间的长度差就消除了。于是，只需要将较短链表遍历两次即可找到交点位置
*/

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if (headA == nullptr || headB == nullptr) {
            return nullptr;
        }
        ListNode *curA = headA;
        ListNode *curB = headB;
        
        while (curA != curB) { 
            curA = curA == nullptr ? headB : curA->next; 
            curB = curB == nullptr ? headA : curB->next; 
        }

        return curA;
    }
};