当前位置: 首页> 教育> 幼教 > 宣城seo_内蒙古最新疫情最新消息今天_免费手机网页制作_如何提高百度关键词排名

宣城seo_内蒙古最新疫情最新消息今天_免费手机网页制作_如何提高百度关键词排名

时间:2025/7/11 11:56:07来源:https://blog.csdn.net/m0_52779966/article/details/145926594 浏览次数:0次
宣城seo_内蒙古最新疫情最新消息今天_免费手机网页制作_如何提高百度关键词排名

题目描述:

 题目中花了很多文字去说明,什么是两条链的相交节点,以及评测系统如何去评价你的程序是否正确,其实简单来说,就是两条链某个节点所指向的内存位置一致,那么就说它们存在相交节点。

给你两个单链表的头节点 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

关键字:宣城seo_内蒙古最新疫情最新消息今天_免费手机网页制作_如何提高百度关键词排名

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: