题目描述:
题目中花了很多文字去说明,什么是两条链的相交节点,以及评测系统如何去评价你的程序是否正确,其实简单来说,就是两条链某个节点所指向的内存位置一致,那么就说它们存在相交节点。
给你两个单链表的头节点 headA
和 headB
,请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点,返回 null
。
图示两个链表在节点 c1
开始相交:
题目数据 保证 整个链式结构中不存在环。
注意,函数返回结果后,链表必须 保持其原始结构 。
自定义评测:
评测系统 的输入如下(你设计的程序 不适用 此输入):
intersectVal
- 相交的起始节点的值。如果不存在相交节点,这一值为0
listA
- 第一个链表listB
- 第二个链表skipA
- 在listA
中(从头节点开始)跳到交叉节点的节点数skipB
- 在listB
中(从头节点开始)跳到交叉节点的节点数
评测系统将根据这些输入创建链式数据结构,并将两个头节点 headA
和 headB
传递给你的程序。如果程序能够正确返回相交节点,那么你的解决方案将被 视作正确答案 。
示例 1:
逻辑:
根据它的特点,就可以想到用哈希集合。先遍历链表A,存储到哈希集合中,再顺序遍历链表B,如果能在遍历过程中找到某个节点能在哈希集合中找到,则表示有相交节点。
还有另外一个有意思的思路(学到了):假设链表A和B有相交点,设置两个指针a,b同时分别遍历
链表A和B,最有意思的设计就是:当a指向NULL后,改变其指向为B的头节点,类似地,将b指向A的头节点,再顺序遍历。这样设计后,a和b将会在某时刻指向同一位置。
在A中相交节点的位置为第4位,也即是说从A的头节点走至相交节点需要3步,而对于B而言则需要走0步。模拟a,b指针的遍历过程,当a走完B又从A走至相交节点一共走了4(Lb)+3=7,对于b而言它走完A后就来到了相交节点,此时b也走了7(La)步。以此作为条件即可判定链表A、B是否有相交节点。
用变量来表示:假设A的节点数为m,因为在节点末尾有NULL节点的存在,所以遍历完A需要走m步,那么在相交节点前方一共有x个节点,也即是说从头节点走至相交节点需要x步。 对于B相应的字母为n和y,那么因A和B有相交节点,所以有已知条件:n-y=m-x;那么减少未知数,y=n-m+x;
首先让a指针开始遍历,当其从B的头节点走到相交节点后,它一共走了m+y=n+x步,那么让b走同样的步数(n+x),会发现b此时也指向相交节点。所以该办法是可行的。
当然如果x=y,也可以推出m=n,也即是说A和B等长,且相交节点在A,B中的位置相同,那么a,b都只需走x步,就可以指向同一位置。
如果两链表无相交节点,那么a和b都会走m+n步,同时都指向NULL。
#if 0
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode *> Haxiset;ListNode * visitor=headA;while(visitor!=NULL){Haxiset.insert(visitor);visitor=visitor->next;}visitor=headB;while(visitor!=NULL){if(Haxiset.find(visitor)!=Haxiset.end()){return visitor;}visitor=visitor->next;}return NULL;}
};
#endif
#if 1
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA==NULL||headB==NULL) return NULL;ListNode *visitor_a=headA,*visitor_b=headB;while(visitor_a!=visitor_b){/*head1不为空时,指针便向后传递如果为空会有两种情况:1,两指针相等,且有交叉2,两指针相等但是都等于空,无交叉*/visitor_a = visitor_a ? visitor_a->next :headB;visitor_b = visitor_b ? visitor_b->next :headA;}return visitor_a;}
};
#endif