当前位置：首页 > article >正文

leetcode142-环形链表

article 2025/1/20 21:10:58

leetcode 142
在这里插入图片描述

方法1 哈希表查找

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

首先定义一个哈希map，然后在每次遍历的时候记录当先的指针，如果发现这个指针已经存在的话，那么说明是环的交点，这个方法比较容易理解，但是空间复杂度消耗较多，因为需要将哈希链表中的每个节点都进行存储

var detectCycle = function(head) {
    const map = new Map()
    let cur = head;
    while(cur && !map.has(cur)){
        map.set(cur,0);
        cur = cur.next;
    }
    return cur;
};

方法2 双指针

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

自己解答本题的时候很自然的利用了哈希来解决，比较容易理解，后面看代码随想录看到双指针法，确实是更加优化的一种方法，将空间复杂度降低到O(1)，不过理解起来更困难，大家可以看代码随想录carl大神的解答：环形链表

var detectCycle = function(head) {
    let fast = head,slow = head;
    while(fast?.next?.next){
        fast = fast.next.next;
        slow = slow.next;
        if(slow === fast){ // 相遇
            let nodeA = slow;
            let nodeB = head;
            while(nodeA!==nodeB){
                nodeA = nodeA.next;
                nodeB = nodeB.next;
            }
            return nodeA;
        }
    }
    // 没找到
    return null;
};