查找链表环结构的入口结点

上吴师兄的算法课,刷leetcode时,遇到了 ‘查找链表环结构的入口结点’这题.

看完 leetcode 的 ‘快慢指针,两次赛跑’(我取的名) 的解法时,一脸懵逼.

结合吴师兄给的示例动图/解析, 并划水整整研究一上午后,

(注:此时作者处于,当前迭代末期,活相对较少,好学生请不要模仿)

总结出了这版 文字纯享,无需公式,让你的直觉接受这种设定! 版算法解析

大家可以先直接去做做原题

(AlgoMooc:环形链表2)[https://www.algomooc.com/746.html]

(力扣:环形链表2(142题))[https://leetcode-cn.com/problems/linked-list-cycle-ii]

题干

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

为了表示给定链表中的环，

我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始).

如果 pos 是 -1，则在该链表中没有环。

注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

懵逼树上懵逼果,懵逼树下你和我

看到这题,第一反应是在结点上做标记,路过一个结点,标记一下.

当然,此时leetcode给出了更优的set储存解法,不影响原本数据.

此处也略提一下,理解简单

// 我想的是在节点上做标记，显然用set更好，记住这思路
var detectCycle = function(head) {
    const visited = new Set();
    while (head !== null) {
        if (visited.has(head)) {
            return head;
        }
        visited.add(head);
        head = head.next;
    }
    return null;
};

重点

此时还给出了第二个更优解法空间复杂度为O(1)

诠释了什么叫我不理解,但我大受震撼.jpg

这里直接讲解法 ‘快慢指针,两次赛跑’

思路是,

第一次, 使用快慢指针, 快指针每次移动2节点, 慢指针每次移动1节点.

当快指针与慢指针第一次相遇时, 当前节点称为相遇点.

第二次, 使用两个慢指针, 慢指针1 从相遇点出发, 慢指针2 从节点头出发,

当两个慢指针第一次相遇时, 此时相遇节点即为环入口点.

无需公式,看完后,让你的直觉接受这种设定!

话不多说,直接上解析,代码在后面

// 要理解 快慢指针 找链的环结构入口,要理解两个重要结论,
// 1.慢指针 走过的的长度 等于 环的长度
// 2.慢指针 从头走到环入口的长度 等于 慢指针 从相遇点走完剩余环的长度

// 假设 快指针 一次走 2个节点,慢指针 一次走 1个节点
// 假设 头到环入口长度 a, 环长度 b.
// 第 1 次相遇时, 快指针总路程 f,慢指针总路程 s,此时可得到两个等式
// (注意是第1次相遇,如果继续跑,第1次相遇后,s每跑1圈,f会跑2圈,会再次在这相遇,算法只需要考虑第1次相遇就行)
// f(快指针路程) = 2s(慢指针走的路程) (快指针是慢指针两倍速)
// f(快指针路程) = s(慢指针走的路程) + b(环的长度)
// 得到 s = b (慢指针走的路程 就是 环的长度b)
// 可理解为,第一次相遇的时候,s还刚进 第1圈,f已经多走了1圈环,所以 s=b
// 所以得到 重要结论 (1) 慢指针路程 s = b 环的节点数

// 接下来要思考,直觉上来说,为什么再次从头开始走一个 慢指针2
// 同时从第一次相遇处 走 慢指针1,两个慢指针必然会在 环入口处相遇?
// 换句话说 为什么 慢指针1 走完 剩余环的长度(y),会等于 从头到入环 的长度?

// 此时,我们整理下, 头到环入口a, 环入口到相遇处(x), 环长度b
// 很显然 环的长度(b) = x(入口到相遇处) + y(相遇处到环入口)
// 同时由结论(1) 环的长度(b) = s(慢指针路径) = a(头到环入口) + x(入口到相遇处)
// x(入口到相遇处) + y(相遇处到环入口) = a(头到环入口) + x(入口到相遇处)

// 语言解释就是, 头到相遇处, 相遇处再到环入口,是等长的,重合部分就是 入口到相遇处
// 路径上来说,都减去重合部分(入口到相遇处x),剩余部分路径相等
// 如果 假设两个慢指针,都不走重合部分,一个从头开始走,一个跳过重合部分从相遇处开始走
// 相同速度,走过相同路径时,便会相遇在入口

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;
        }
        if (fast === slow) {
            let ptr = head;
            while (ptr !== slow) {
                ptr = ptr.next;
                slow = slow.next;
            }
            return ptr;
        }
    }
    return null;
};