首页 > 代码库 > Linked List Cycle
Linked List Cycle
https://leetcode.com/problems/linked-list-cycle/#/description
首先想到的思路就是,用hash 表来存下每个node 的指针,然后遍历链表,每个node 都去哈希表里查一下,如果之前遇到过就说明链表是有圈的。
另一个思路比较有启发性,就是看看操场上跑步的人,如果操场是个圈,那么从同一起点出发,两个速度不一样的人,总会在某一点再次相遇。
如果不是一个圈,那么跑得快的人会最先到达重点,两人永远不会再相遇(sad
所以思路就是,维护两个指针,一个快指针,一个慢指针。快指针每次迭代都往前走一步,但是慢指针每两次迭代才走一步。注意这里指针更新的方式
一定要保证每个node 都踩过,不能跳指针(当然在链表里一次往前走两个node 是反直觉的
这样可以证明,如果链表有圈的话,两个指针总会在某个点相遇。
var hasCycle = function(head) { if (head == null) return false; var slow_go = 0; var fast = head.next; var slow = head; while (fast != null && fast != slow) { if ((++slow_go) % 2 === 0) { slow = slow.next; } fast = fast.next; } return fast == slow;};
Linked List Cycle
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。