临沂网站设计哪家好,wordpress 加入地图,学习教建网站,搜外网141. 环形链表 - 力扣#xff08;LeetCode#xff09; 1. 什么是快慢指针 这里我们我们将介绍环形链表的经典解法——快慢指针#xff0c;简单理解#xff0c;指针移动快的叫做快指针fast#xff0c;移动速度慢的叫慢指针slow。一般我们设快指针走两步#xff0c;慢指针走…141. 环形链表 - 力扣LeetCode 1. 什么是快慢指针 这里我们我们将介绍环形链表的经典解法——快慢指针简单理解指针移动快的叫做快指针fast移动速度慢的叫慢指针slow。一般我们设快指针走两步慢指针走一步。 如果你对快慢指针理解或应用不太了解可以参照下面几篇文章去力扣练习。
LeetCode - 26. 删除有序数组中的重复项 C语言快慢指针配图-CSDN博客
LeetCode - 27. 移除元素 C语言快慢指针配图-CSDN博客 通过下图我们可以清晰地知道当fast走两步slow走一步时如果这是一个环形链表那么它们总有一天会遇见。
2. 非环形链表 那么我们来看一下非环形链表长什么样通过下面这幅图片我们可以知道非环形链表那么fast或fast-next 一定为空这与元素个数有关。 当然这也是一道经典的链表中间节点的题目876. 链表的中间结点 - 力扣LeetCode 3.代码展示 通过上面两个铺垫我们知道了 1.怎么判断是否为环形链表2.非环形链表的结束条件
/*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/
bool hasCycle(struct ListNode *head) {struct ListNode* fast head;struct ListNode* slow head;while(fast fast-next){fast fast-next-next;slow slow-next;if(fast slow){return true;}}return false;
}
4.扩展fast走3步slow走一步呢 这里我们先给出结论不论fast走几步slow走几步如果是环形链表那么它们一定会相遇。这真是令人感动。 总结一下 1. 如果N是偶数第一轮就相遇 2. 如果N是奇数C是偶数第一轮错过第二轮就能相遇 3.如果N是奇数C是奇数永远追不上但这里的条件永远不能成立可以自己代入上面fast走3步slow走1步公式 2L n * C - N
