Swift 数据结构与算法( 27) 链表 + Leetcode142. 环形链表 II(双指针)

Swift 数据结构与算法( ) 数组 + Leetcode

概念

这一题的关键概念和应用归纳如下：

1. 快慢指针技巧 (Floyd's Cycle Detection Algorithm)：这是一种使用两个移动速度不同的指针来检测循环（在这种情况下，是链表中的环）的技巧。这种方法不仅可以确定链表是否有环，还可以找到环的起始位置。

2. 数学推导：在确定存在环之后，我们利用了数学和逻辑推导来确定环的起始位置。这包括了对环内外的距离进行比较，以及对快指针和慢指针的移动速度和距离的理解。

3. 空间效率：此方法仅使用常数额外空间，即 O(1) 的空间复杂度，使其在处理大数据时非常高效。

实际应用：

1. 循环检测：除了链表，快慢指针技巧还可以应用于其他数据结构中，如数组，来检测循环或重复。

2. 资源泄露诊断：在计算机程序中，如果存在不再需要但仍然被引用的对象，则可能会导致内存泄露。此技巧可以用于诊断此类问题。

3. 网络诊断：在计算机网络中，数据包可能会在网络中的某些环路中被困。快慢指针技巧可以用于模拟并诊断此类问题。

4. 周期性模式识别：在金融、气象学和其他领域中，数据可能会显示出周期性模式。此技巧可以帮助在数据中识别这些模式。

总之，本题不仅提供了一个解决链表问题的方法，还引入了一种在计算机科学和其他领域中都非常有用的技巧。

错误提示

总结一下代码中的问题：

这个循环条件是错误的。实际上希望循环继续，直到 fast 和 slow 指针相遇或者 fast 或 fast?.next 变为 nil。正确的条件应该是:

Create FileswiftCopy code
while fast != nil && fast?.next != nil && fast !== slow {
    ...
}

1. 循环的初始条件：在的原始代码中，当尝试检测链表中的环时，while 循环的条件是不正确的。问题在于初始条件，因为设置了 slow 和 fast 都指向 head，所以在循环的第一次迭代时，fast !== slow 评估为 false，导致循环不执行。

   错误的代码：

   while fast != nil && fast !== slow {
       slow = slow?.next
       fast = fast?.next?.next
   }
   

   应该首先移动 slow 和 fast 指针，然后再检查它们是否相等。

   修正后的代码：

   while fast != nil && fast?.next != nil {
       slow = slow?.next
       fast = fast?.next?.next
       if slow === fast {
           break
       }
   }
   

2. 接下来的检查是正确的。如果 slow 和 fast 指针没有相遇，那么链表中没有环：

Create FileswiftCopy code
// If there's no cycle, return nil
if slow !== fast {
    return nil
}

判断链表是否有环

可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇 ，说明这个链表有环。

为什么fast 走两个节点，slow走一个节点，有环的话，一定会在环内相遇呢，而不是永远的错开呢

首先第一点：fast指针一定先进入环中，如果fast指针和slow指针相遇的话，一定是在环中相遇，这是毋庸置疑的。

那么来看一下，为什么fast指针和slow指针一定会相遇呢？

可以画一个环，然后让 fast指针在任意一个节点开始追赶slow指针。

会发现最终都是这种情况， 如下图：

fast和slow各自再走一步， fast和slow就相遇了

这是因为fast是走两步，slow是走一步，其实相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。

动画如下：

如果有环，如何找到这个环的入口

此时已经可以判断链表是否有环了，那么接下来要找这个环的入口了。

假设从头结点到环形入口节点 的节点数为x。 环形入口节点到 fast指针与slow指针相遇节点 节点数为y。 从相遇节点 再到环形入口节点节点数为 z。 如图所示：

那么相遇时： slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针， （y+z）为 一圈内节点的个数A。

因为fast指针是一步走两个节点，slow指针一步走一个节点， 所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

(x + y) * 2 = x + y + n (y + z)

两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示 头结点到 环形入口节点的的距离。

所以要求x ，将x单独放在左面：x = n (y + z) - y ,

再从n(y+z)中提出一个 （y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢？

先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这里补充一下 即使n不为 1, 举例为 2

x = 2Z + y

那么, z + y = 一圈 的圆环举例.

两个新的 指针, 仍然会在圆环起点相遇. 等于多走了一个圆环而已.

这就意味着，从头结点出发一个指针，从相遇节点 也出发一个指针，这两个指针每次只走一个节点， 那么当这两个指针相遇的时候就是 环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。

让index1和index2同时移动，每次移动一个节点， 那么他们相遇的地方就是 环形入口的节点。

动画如下：

题目

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

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

不允许修改 链表。

 

示例 1：

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

示例 2：

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

示例 3：

输入： head = [1], pos = -1
输出： 返回 null
解释： 链表中没有环。

 

提示：

• 链表中节点的数目范围在范围 [0, 104] 内
• -105 <= Node.val <= 105
• pos 的值为 -1 或者链表中的一个有效索引

解题思路🙋🏻‍ ♀️

边界思考🤔

代码

class Solution {
    // 定义一个方法检测链表中的环
    func detectCycle(_ head: ListNode?) -> ListNode? {
        // 如果链表是空的或者只有一个节点，直接返回nil（无环）
        if head == nil || head?.next == nil {
            return nil
        }
        
        // 初始化两个指针：慢指针和快指针，都从头节点开始
        var slow: ListNode? = head
        var fast: ListNode? = head
        
        // 当快指针及其下一个节点不为nil时，持续循环
        while fast !== nil && fast?.next !== nil {
            // 慢指针每次移动一个节点
            slow = slow?.next
            // 快指针每次移动两个节点
            fast = fast?.next?.next
            // 如果两指针相遇，表示存在环，跳出循环
            if slow === fast {
                break
            }
        }
        
        // 如果循环结束后，慢指针与快指针不相等，表示链表中没有环
        if slow !== fast {
            return nil
        }
        
        // 将慢指针重新设置为头节点
        slow = head
        // 同时移动慢指针和快指针，直到它们再次相遇
        while slow !== fast {
            slow = slow?.next
            fast = fast?.next
        }
        
        // 返回环的起始节点
        return slow
    }
}

时空复杂度分析

O(n)

引用

本系列文章部分概念内容引用 www.hello-algo.com/

解题思路参考了 abuladong 的算法小抄, 代码随想录... 等等

Youtube 博主: huahua 酱, 山景城一姐,