手机在线做ppt的网站,广州网站设计成功刻,南京搭建公司,软件外包专业学什么文章目录题目描述思路 代码更新版三刷 - 再更新题目描述
相对于环形链表#xff0c;这里要求找到环的起点难点在于 O(1)#xff0c;否则可以直接哈希表冲
思路 代码
找出快慢指针的路程关系#xff0c;得出结论#xff08;详见代码注释#xff09;
/*** …
文章目录题目描述思路 代码更新版三刷 - 再更新题目描述
相对于环形链表这里要求找到环的起点难点在于 O(1)否则可以直接哈希表冲
思路 代码
找出快慢指针的路程关系得出结论详见代码注释
/*** Definition for singly-linked list.* class ListNode {* int val;* ListNode next;* ListNode(int x) {* val x;* next null;* }* }*/// 相遇时结束fastDistance 2 * slowDistance两倍路程
// fastDistance slowDistance n * b 比 slow 多走 n 圈
// 》slowDistance n * b
public class Solution {public ListNode detectCycle(ListNode head){// 空链表ListNode slow head, fast head;while(true){// 无环情况if(fast null || fast.next null){return null;}slow slow.next;fast fast.next.next;if(fast slow){break;}}// 令 fastDistance 0此时 slowDistance n * b// 只要令 slowDistance a n * b即可走到环起点fast head;while(fast ! slow){fast fast.next;slow slow.next;}return fast;}
}更新版
虽然但是感觉有稍微优化了一下 while 结构
public class Solution {public ListNode detectCycle(ListNode head) {ListNode slow head, fast head;do {if(fast null || fast.next null) {return null;}slow slow.next;fast fast.next.next;} while(slow ! fast);fast head;while(fast ! slow) {fast fast.next;slow slow.next;}return fast;}
}三刷 - 再更新
选取了一个我更喜欢的结构成环情况直接开找然后return
public class Solution {public ListNode detectCycle(ListNode head) {ListNode fast head, slow head;while(fast ! null fast.next ! null) {fast fast.next.next;slow slow.next;if(fast slow) {fast head;while(fast ! slow) {fast fast.next;slow slow.next;}return fast;}}return null;}
}
