141. 环形链表

[devinxiang]

描述

方案一，哈希存储

思路：通过 map 把走过的节点存起来，如果重复走则可确认是环

var hasCycle = function(head) {
    if(!head) return false;
    let map = new Map();
    while(head){
        if (map.has(head)) return true;
        map.set(head);
        head = head.next;
        if (head === null) return false;
    }
};

• 时间复杂度：O(n)
• 空间复杂度：O(n)

方案二，双指针

思路：构建快慢指针，慢指针每次走一个，快指针走两个，如果有环快指针一定会跟慢指针相遇；

var hasCycle = function(head) {
    if (!head || !head.next) return false;
    let flow = head;
    let fast = head.next;
    while (fast !== null && fast.next) {// 判断走的快的是否已经到达了终点
        if (flow === fast) return true;
        flow = flow.next;
        fast = fast.next.next;
        if (fast === flow) {
            return true;
        }
    }

    return false;
}