环形链表 II

时间：2022-10-08 10:16:16

LeetCode 75 学习计划适用于想为技术面试做准备但不确定应该聚焦于哪些题目的用户。学习计划中的题目都是经过精心挑选的，Level 1和 Level 2 学习计划是为初级用户和中级用户准备的，题目覆盖了大多数中层公司面试时所必需的数据结构和算法，Level 3 学习计划则是为准备面试*公司的用户准备的。​​来源​​

第 5 天

​​环形链表 II​​

难度：中等

题目

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

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

环形链表 II

输入： head = [3,2,0,-4], pos = 1
输出： 返回索引为 1 的链表节点
解释： 链表中有一个环，其尾部连接到第二个节点。

题解

判断一个链表是否成环。

function ListNode(val){
    this.val = val
    this.next = null
}

我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。

然后把快指针放到头，和慢指针一起走，他们再次相遇的位置就是环的入口！

为什么是这样？我们可以参考下图：

环形链表 II

设环的入口是 L 长度，那么慢指针走的距离是 L，快指针走的则是 2L，设整个路径长度是 D，第一次相遇的距离是 D - L，剩下的距离是 (D-(D-L))，也就是 L ，这也就解释了为什么 设的 L 是对的。

这里有个视频讲解，很清晰。-> ​​https://leetcode.cn/problems/linked-list-cycle-ii/solution/142-huan-xing-lian-biao-ii-by-chen-wei-f-g157/​​

var detectCycle = function(head) {
    if (head === null) {
        return null;
    }
    let slow = head, fast = head;
    while (fast !== null) {
        slow = slow.next;//慢指针移动两步，快指针移动一步
        if (fast.next !== null) {
            fast = fast.next.next;
        } else {
            return null;//如果没有环 之间返回null
        }
        if (fast === slow) {//有环
            let fast = head;
            //快指针指向头节点，然后每次快慢指针各走一步直到相遇，相遇的节点就是入环节点
            while (fast !== slow) {
                fast = fast.next;
                slow = slow.next;
            }
            return fast;
        }
    }
    return null;
};

总结

记住，这类链表题目一般都是使用双指针法解决的，例如寻找距离尾部第K个节点、寻找环入口、寻找公共尾部入口等。

标签：

相关文章