Swift 数据结构与算法( ) 数组 + Leetcode
概念
这一题的关键概念和运用归纳如下：
-
快慢指针技巧 (Floyd’s Cycle Detection Algorithm)：这是一种运用两个移动速度不同的指针来检测循环（在这种状况下，是链表中的环）的技巧。这种办法不只能够确认链表是否有环，还能够找到环的开端方位。
-
数学推导：在确认存在环之后，咱们利用了数学和逻辑推导来确认环的开端方位。这包括了对环表里的间隔进行比较，以及对快指针和慢指针的移动速度和间隔的了解。
-
空间效率：此办法仅运用常数额定空间，即 O(1) 的空间复杂度，使其在处理大数据时十分高效。
实践运用：
-
循环检测：除了链表，快慢指针技巧还能够运用于其他数据结构中，如数组，来检测循环或重复。
-
资源走漏确诊：在计算机程序中，假如存在不再需求但仍然被引用的目标，则可能会导致内存走漏。此技巧能够用于确诊此类问题。
-
网络确诊：在计算机网络中，数据包可能会在网络中的某些环路中被困。快慢指针技巧能够用于模拟并确诊此类问题。
-
周期性形式辨认：在金融、气象学和其他领域中，数据可能会显示出周期性形式。此技巧能够协助在数据中辨认这些形式。
总归，本题不只提供了一个处理链表问题的办法，还引入了一种在计算机科学和其他领域中都十分有用的技巧。
错误提示
总结一下代码中的问题：
这个循环条件是错误的。实践上希望循环继续，直到 fast 和 slow 指针相遇或许 fast 或 fast?.next 变为 nil。正确的条件应该是:
Create FileswiftCopy code
while fast != nil && fast?.next != nil && fast !== slow {
...
}
-
循环的初始条件：在的原始代码中，当尝试检测链表中的环时，
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 } } -
接下来的查看是正确的。假如
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 酱, 山景城一姐,
