相交链表Leetcode

心已赠人 2022-10-06 02:59 145阅读 0赞

## 一、题目 ##

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。
    换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。
    
    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 二、题解 ##

根据题意,两个链表相交的点是指: 该结点既在A链表上又在B链表上,说明A和B是相交的，而对于相交的情况,两条链表一定是这种结构:  
![在这里插入图片描述][20210610235433218.png_pic_center]  
因为如果链表A和链表B相交于D的话,那么说明D结点即在A上又在B上,而D之后的元素自然也就均在A和B上了,因为他们是通过next指针相连的。

如果有相交的结点D的话,每条链的头结点先走完自己的链表长度,然后回头走另外的一条链表,那么两结点一定为相交于D点,因为这时每个头结点走的距离是一样的,都是 **AD + BD + DC**,而他们每次又都是前进1,所以距离相同,速度又相同,固然一定会在相同的时间走到相同的结点上,即D点.

当链表A和B没有交点时，如下图所示。按照同样的方法，最后会在结点a和结点b会同时到达D点和C点，此时a=b=nullptr，退出循环，返回nullptr（即此时的a），表示无相交。  
![在这里插入图片描述][20210611001443829.png_pic_center]

## 三、C++实现 ##

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    
    class Solution { 
    public:
        ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { 
            ListNode* a = headA;
            ListNode* b = headB;
            while (a != b)
            { 
                a = a != nullptr ? a->next : headB;
                b = b != nullptr ? b->next : headA;
            }
            return a;
        }
    };

[20210610235433218.png_pic_center]: /images/20221005/ebc188e88ea6437c9ae6da6b406549fb.png
[20210611001443829.png_pic_center]: /images/20221005/c7769e473ae64a429885235546aab8f8.png