142.形链表2

LeetCode

暴力解法 哈希表

保存每一个节点判断

var detectCycle = function(head) {
   var map = new Map();
   var cur = head;
    while(cur!==null){
        if(map.get(cur)===cur){
            return cur;
        }
        map.set(cur,cur);
        cur = cur.next;
    }
    return null;
};

复杂度分析

• 时间复杂度：

• 空间复杂度：

双指针

快慢指针同时移动，第一次相遇后，定义新指针为头节点，新指针和慢指针同时移动，再次相遇时的节点为入环节点

通过数学演变来确认双指针的正确性,如下图

• 设慢指针的移动速度为，快指针的移动速度为,用 来表示走过的步数

• 那么慢指针走到相遇点的时候走过,快指针走过了

• 可以得到

• 所以从相遇点到入环点的步数和从头节点到入环的步数是相同的

var detectCycle = function(head) {
    var fast = head;
    var slow = head;
    var res = head;
    while(fast!==null && fast.next!==null){
        fast = fast.next.next;
        slow = slow.next;
        if(slow===fast){
            while(res!==fast){
                res = res.next;
                fast = fast.next;
            }
            return res;
        }
    }
    return null;
};

复杂度分析

• 时间复杂度：

• 空间复杂度：

打赏