【 Day 11 】2021-05-20 - 142. 环形链表 II

题目描述

142. 环形链表 II

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/linked-list-cycle-ii/

前置知识

暂无

题目描述

给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

进阶：

你是否可以使用 O(1) 空间解决此题？

我的回答

解法一

时空复杂度

时间复杂度：O(n)

空间复杂度: O(n)

链表问题首先使用Map记录结点，有环就会重复走一个结点

var detectCycle = function (head) {
    let map = new Map()
    while (head) {
        if (map.has(head)) return head
        map.set(head, 1)
        head = head.next
    }
    return null
};

解法二

时空复杂度

时间复杂度：O(n)

空间复杂度: O(1)

快慢指针，快慢指针第一次相遇的时候，头结点和慢指针离入环点的距离相等

var detectCycle = function (head) {
    let slow = head
    let fast = head
    while (fast) {
        slow = slow.next
        if (!fast.next) return null
        fast = fast.next.next
        if (fast !== slow) continue
        let pre = head
        while (pre !== slow) {
            pre = pre.next
            slow = slow.next
        }
        return slow
    }
    return null
};

参考回答