前言

本系列主要整理面试中需要掌握的手撕代码题。本节介绍链表中有环的问题。

---

一、BM6 判断链表中是否有环

（1）设置快慢指针，快指针一次走两格，慢指针一次走一格；
（2）如果快指针不为空，那么就一直循环着；
（3）如果快指针等于慢指针，证明链表中有环，如果快指针为空，则证明链表中没有环。

function hasCycle( head ) {
    // write code here
    var slow = head;
    var fast = head;
    while(fast && fast.next){
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast) return true
    }
    return false
}
1
2
3
4
5
6
7
8
9
10
11

二、BM7 链表中环的入口结点

（1）设置快慢指针，快指针一次走两格，慢指针一次走一格；
（2）与上题相同，如果快指针 == 慢指针，则证明有环，如果快指针为空，则无环；
（3）如果快指针等于慢指针，则令慢指针从头开始，两个指针都一次一格向前走，当快指针等于慢指针时，该位置就是环的开头。