珠海做网站哪间好,wordpress移动端页面模板下载,wordpress如何采集优酷,电商网站定制开发一、题目描述 题目链接#xff1a;力扣#xff08;LeetCode#xff09;官网 - 全球极客挚爱的技术成长平台 二、题解
解题思路#xff1a; 快慢指针#xff0c;即慢指针一次走一步#xff0c;快指针一次走两步#xff0c;两个指针从链表起始位置开始运行#xff0c;…一、题目描述 题目链接力扣LeetCode官网 - 全球极客挚爱的技术成长平台 二、题解
解题思路 快慢指针即慢指针一次走一步快指针一次走两步两个指针从链表起始位置开始运行如果链表带环则一定会在环中相遇否则快指针率先走到链表的末尾。 扩展 1、为什么快指针每次走两步慢指针走一步可以 假设链表带环两个指针最后都会进入环快指针先进环慢指针后进环。当慢指针刚进环时可能就和快指针相遇了最差情况下两个指针之间的距离刚好就是环的长度。此时两个指针每移动一次之间的距离就缩小一步不会出现每次刚好是套圈的情况因此在慢指针走到一圈之前快指针肯定是可以追上慢指针的即相遇。 2、快指针一次走3步走4步...n步行吗 所以解决该题时我们使用快慢指针即慢指针一次走一步快指针一次走两步两个指针从链表起始位置开始运行如果链表带环则一定会在环中相遇。
三、代码
public class Solution {public boolean hasCycle(ListNode head) {ListNode fast head;ListNode slow head;while (fast ! null fast.next !null) {fast fast.next.next;slow slow.next;if(fast slow) {return true;}}return false;}
}
另一种写法 public boolean hasCycle2(ListNode head) {ListNode fast head;ListNode slow head;while (fast ! null fast.next !null) {fast fast.next.next;slow slow.next;if(fast slow) {break;}}if (fast null||fast.next null) {return false;}return true;}
