运城网站制作公司,成crm软件,2022网页游戏排行榜前十,国家级示范校建设网站文章目录 一.什么是环形链表#xff1f;二.环形链表的例题#xff08;力扣#xff09; 三.环形链表的延伸问题 补充 一.什么是环形链表#xff1f; 环形链表是一种特殊类型的链表数据结构#xff0c;其最后一个节点的下一个指针指向链表中的某个节点#xff… 文章目录 一.什么是环形链表二.环形链表的例题力扣 三.环形链表的延伸问题 补充 一.什么是环形链表 环形链表是一种特殊类型的链表数据结构其最后一个节点的下一个指针指向链表中的某个节点形成一个闭环。 换句话说链表的最后一个节点连接到了链表中的某个中间节点而不是通常情况下连接到空指针 (null) 二.环形链表的例题力扣 给你一个链表的头节点 head 判断链表中是否有环。 如果链表中有某个节点可以通过连续跟踪 next 指针再次到达则链表中存在环。 为了表示给定链表中的环评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置索引从 0 开始。注意pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。 如果链表中存在环 则返回 true 。 否则返回 false 。 输入head [3,2,0,-4], pos 1
输出true
解释链表中有一个环其尾部连接到第二个节点。这个题目我们的做法是快慢指针思想先设置fast和slow两个指针指向链表的开始慢的一次走一步快的一次走两步如果不带环fast的就为空如果带环fast就会在环里追上slow。我们来画图来看他的情况。
就是这4种情况然后写代码就可以了这个并不难 。
bool hasCycle(struct ListNode* head)
{struct ListNode* slow head, * fast head;while (fast fast-next)//存在奇偶{slow slow-next;fast fast-next-next;if (slow fast)//相交就是环{return true;}}return false;
}
三.环形链表的延伸问题 1.为什么fast和slow一定会在环里相遇会不会在还里面错过或者永远追不上 2.为什么一定是slow走一步fast走两步难道不能slow一步fast走其他步数 3.如何去求入环口的节点呢 3.1.为什么fast和slow一定会在环里相遇会不会在还里面错过或者永远追不上 slow和fast一定是fast先入环这时候slow走了入环前距离的一半随着slow进环fast已经在环里走了一段距离了走的多少和环的大小是有关系的我们假设slow进环的时候离fast距离为N快的开始追慢的慢的每次走一步快的每次走两步就相当于追y一步所以说他的距离变化是NN-1N-2。。。10他们之间的距离为零时就是相遇点所以说一定追得上。 3.2为什么一定是slow走一步fast走两步难道不能slow一步fast走其他步数 假设slow一步fast3步slow近环之后他们的距离为N则他们的距离变化为当N为偶数是NN-2N-4…..02。可以追得上但是N为奇数的时候N的变化为NN-2N-4..1-1。如果因为奇数距离为-1意味着他们之间的距离变成了c-1c是环的长度那么就要重新追但是你重新追的话你就需要判断c-1他是不是二的倍数如果它是的话就可以追上不是的话就追不上。 在假设slow一步fast4步追3步其实也是一样的如果N是3的倍数就可以追上但是N不是3的倍数的话就要看有两种情况一种是NN-3N-6..2-1。一种为NN-3N-6..1-2。根据之前的结论如c-1和c-2是3的倍数的话就可以追上 3.3如何去求入环口的节点呢
先说结论:一个指针从相遇点开始走一个指针从链表头开始走他们会在环的入口点相遇。 追上的相遇的过程中慢指针的距离LX快指针的距离LNCX,因为你不知道fast在环里多跑了几圈所以设了一个N但是N肯定1,又因为fast是slow的两倍所以2(LX)LNCX。整理可得L(N-1)XC-X(N-1)X就是从meetNode开始又走到meetNode的距离C-X就是从相遇点到入口点的距离结论得证。 struct ListNode* deCycle(struct ListNode* head)
{struct ListNode* slow head, * fast head;while (fast fast-next){slow slow-next;fast fast-next-next;//相遇了if (slow fast){struct ListNode* meet slow;//由公式得证while (meet ! head){meet meet-next;head head-next;}return meet;}}return NULL;} 补充
其实求入口点还有一种方法就是在入口点处直接指向空指针把它看作一个相交链表来做由头节点和相遇点之前的那个节点然后两个节点找相交点就可以了。
