快慢指针及原理证明(swift实现)

链表

链表的结构很简单，由指针把若干个节点连接成链状结构。链表是一种动态的数据结构，因为在创建链表时，无须知道链表的长度。当插入一个节点时，我们只需为新节点分配内存，然后调整指针的指向来确保新节点被链接到链表当中。内存分配不是在创建链表时一次性完成，而是在每添加一个节点分配一次内存。由于没有闲置的内存，链表的空间效率比数组高。

public class ListNode {
    public var val: Int
    public var next: ListNode?
    public init() { self.val = 0; self.next = nil; }
    public init(_ val: Int) { self.val = val; self.next = nil; }
    public init(_ val: Int, _ next: ListNode?) { self.val = val; self.next = next; }
}

快慢指针

一、快慢指针基本介绍

快慢指针是一种双指针技巧，常用于遍历链表或是数组。顾名思义，就是两个指针同时遍历链表，但移动速度不同，一个走得快，一个走得慢，根据问题的需要来确定指针指向的位置和指针的走向、速度。使用快慢指针算法可以极大简化算法的时间复杂度，提高程序的效率。

注意： 这里的快慢指针并不是严格的指针类型，而是可以指向具体位置的变量，一般在数组中使用下标，在链表中使用链表的节点指针。

二、快慢指针之找特殊节点

简介：快慢指针一般可以用来找特殊节点的位置，一般让快慢指针相隔一定距离，当快指针走到尾时，慢指针则停在你要找的位置上。

经典例题：

1.删除链表的倒数第k个结点

题目描述

给你一个链表，删除链表的倒数第 k 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], k = 2 输出：[1,2,3,5]

---

示例 2：
输入：head = [1], k = 1 输出：[]

---

示例 3：
输入：head = [1,2], k = 1 输出：[1]

---

数据范围：
链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= k <= sz

---

进阶：你能尝试使用一趟扫描实现吗？

解题思路

• 解法1——遍历2次链表
  为了得到倒数第$k$个节点，很自然的想法是先走到链表的尾端，再从尾部回溯$k$步。可是我们从链表节点的定义可以看出，本题中的链表是单向链表，单向链表的节点只有从前往后的指针没有从后往前的指针，因此这种思路行不通。既然不能从尾节点开始遍历这个链表，我们还是把思路回到头节点上来。假设整个链表有$n$个节点，那么倒数第$k$个节点就是从头节点开始的第$n-k+1$个节点。如果我们能够得到链表中节点的个数$n$，那么只要从头节点开始往后走$n-k+1$步就可以了。如何得到节点数$n$？只需从头开始遍历链表，每经过一个节点，计数器加1即可。也就是说我们需要遍历链表两次，第一次统计出链表中节点的个数$n$，第二次就能找到倒数第$k$个点。

以head = [1,2,3,4,5], k = 3为例 —> [1,2,4,5]

• 解法2——遍历1次链表

为了实现制遍历链表一次就能找到倒数第k个节点，我们可以利用快慢指针算法。先让快指针先走$k$步，然后让快慢指针同时走，当快指针走到链表的尾部时，慢指针停在倒数第$k$个节点。

小技巧：涉及链表删除操作的可以加一个虚拟头节点来防止删除节点为链表的头节点、删完为空等特殊情况，可以减少特判。

退回前一步

    func removeNthFromEnd(_ head: ListNode?, _ n: Int) -> ListNode? {
        guard head != nil, n > 0 else {
            return nil
        }
      
        var dummy = ListNode(-1)
        dummy.next = head
        var fast: ListNode? = dummy
        var slow: ListNode? = dummy
        for _ in 1...n {
            fast = fast?.next
        }
        
        while fast?.next != nil {
            fast = fast?.next
            slow = slow?.next
        }
        slow?.next = slow?.next?.next
        return dummy.next
    }

2.链表的中间节点

题目描述

给你单链表的头结点 head ，请你找出并返回链表的中间结点。

如果有两个中间结点，则返回第二个中间结点。

示例 1：

输入：head = [1,2,3,4,5]
输出：[3,4,5]
解释：链表只有一个中间结点，值为 3 。

---

示例 2：

输入：head = [1,2,3,4,5,6]
输出：[4,5,6]
解释：该链表有两个中间结点，值分别为 3 和 4 ，返回第二个结点。

---

数据范围：
链表的结点数范围是 [1, 100]
1 <= Node.val <= 100

解题思路

• 解法1——遍历2次链表

先遍历一次链表算出长度，并对链表长度为奇数还是偶数做分类处理，通过计算后再次遍历链表，返回中间节点。

• 解法2——遍历1次链表

使用快慢指针的方法只需遍历一次链表，让快指针一次走两步，慢指针一次走一步，当快指针走到尾时，慢指针则停在题目需要的位置，也无需对链表长度做分类处理。

链表长度为奇数，slow在中间结点，fast在最后一个节点上

链表长度为偶数，slow在第二个中间结点，fast指向NULL

    func middleNode(_ head: ListNode?) -> ListNode? {
        var slow = head
        var fast = head
        
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        
        return slow
    }

判断链表的长度是否为奇数：如果fast非NULL，说明长度为奇数

    func isLengthOdd(_ head: ListNode?) -> Bool {
        var slow = head
        var fast = head
        
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        
        return fast != nil // 如果fast非NULL，说明长度为奇数
    }

三、快慢指针之环形问题

简介：快慢指针还可以解决带环问题，例如判断链表是否带环，或返回链表入环的第一个节点。

经典例题：

1.判断环形链表

题目描述

给你一个链表的头节点 head ，判断链表中是否有环。

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

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

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

---

示例 2：

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

---

示例 3：

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

---

数据范围：
链表中节点的数目范围是 $[0,10^4]$
$-10^5\le Node.val\le 10^5$
pos为-1 或者链表中的一个 有效索引 。

---

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

解题思路

定义两个快慢指针，慢指针一次走一步，快指针一次走两步，如果链表有环，快指针和慢指针最终会相遇；如果没有环，快指针将会到达链表的末尾（即指向NULL）。

不带环

fast指向NULL，slow指向中点

带环

fast 和 slow 在环上某点相遇

---

A 是起点，B 是环的入口，slow刚走到入环点 B 时，fast在环中走了$n$圈最终的位置为 C，AB 之间的距离是$x$，从 B 点顺时针走到 C 的距离是$y$，从 C 点顺时针走到 B 的距离是$z$。环的总长度$s=y+z$。

---

Q1:链表有环的情况下，为什么快慢指针一定会相遇？

假设slow刚走到入环点 B 时，fast的刚好走到 C ，此时两个指针的距离为$z$。

而fast每次走两步，slow每次走一步，快指针速度差为1，则每走一次，二者之间的距离就减1。所以经过z次移动，两者一定会相遇。

打个比方来理解slow，fast之间的关系，好比在环形跑道上 A 同学和 B 同学之间距离未知，但 A 同学的速度是 B 同学的两倍，在未来的某一时刻两者一定会相遇。

Q2:快指针速度差不为一时，是否会永远不相遇？

以 fast每次走3步 slow每次走1步 为例：

fast每次走3步，slow每次走1步，快指针速度差为2，则每走一次，二者之间的距离就减2。

• 经过$k$次之后两者之间的距离为$z-2k$。

  • 当$z$为偶数时，则距离一定会变为0，即相遇；

  • 当$z$为奇数时，则距离会逐渐递减为-1（N-2, N-4, …, 3, 2, -1）（这里的-1是指fast领先slow指针一步），两指针错过。那么接下去fast和slow还会不会相遇呢？

假设环的总长度$s$，则此时两个指针的距离变成$s-1$，同理

• 当$s-1$为偶数时，即$s$为奇数时，则一定会相遇

  • 当$s-1$为奇数时，即$s$为偶数时，则二者之间的距离最终又会变为-1，一直错过无法相遇。

总结：当$z$为奇数，$s$为偶数时，二者一直错过，无法相遇。

s是偶数且z是奇数，这个条件能同时满足吗？

当slow刚走到入环点 B 时，走过的路程用$L\_slow$表示，则有$L\_slow=x$，fast走过的路程用$L\_fast$表示，则有$L\_fast=x+ns+s-z$。

因为fast每次走3步 slow每次走1步 ，所以有：

$$\begin{array}{rl}3L\_slow& =L\_fast\\ 3x& =x+ns+s-z\\ 2x& =(n+1)s-z\\ z& =(n+1)s-2x\end{array}$$

$s$是偶数，$2x$也是偶数，偶数减偶数一定是偶数，所以$z$一定是偶数，不可能是奇数，所以此条件不可能同时成立，fast与slow一定会相遇。

fast每次走k步 slow每次走1步的情况以此类推。只要slow每次走1步，fast每次走比slow快，就一定会相遇。

slow每次走的步数不是1呢？
AI给出的答案是依旧一定会相遇，证明就交给读者自行思考了。

---

如果fast每次移动 $k$步，slow每次移动 $s$ 步（其中 $k>s\ge 1$），它们的相对速度是 $k-s$。假设一共走了$t$次，两者在环上的某点相遇时，fast走了$n\_1$圈，slow走了$n\_2$圈，环的长度为$l$，则两者的总路程之差为$(n\_1-n\_2)\cdot l$。令$n=n\_1-n\_2$，则有$n\cdot l=(k-s)\cdot t$。
即：$(k-s)\cdot t=n\cdot l$【其中$k,s,l$是正整数 $k>s\ge 1$ 】证明恒有整数解$t$和整数解$n$。

---

AI证明过程如下：

    func hasCycle(_ head: ListNode?) -> Bool {
        var fast = head
        var slow = head
        
        while fast != nil && fast?.next != nil {
            fast = fast?.next?.next
            slow = slow?.next
            
            if fast === slow {
                return true
            }
        }
        return false
    }

2.判断环形链表并返回入环节点

题目描述

给定一个链表的头节点 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,10^4]$内
$-10^5\le Node.val\le 10^5$
pos为-1 或者链表中的一个 有效索引 。
进阶：你是否可以使用 O(1) 空间解决此题？

解题思路

• 解法1——(链表，快慢指针扫描) 时间复杂度 O(n) 空间复杂度 O(1)

用两个指针 slow、fast分别从起点开始走，slow每次走一步，fast每次走两步。如果过程中 fast走到nil，则说明不存在环。否则当 slow 和 fast相遇后，让slow返回起点，fast待在原地不动，然后两个指针每次分别走一步，当再次相遇时，相遇点就是环的入口。

证明：如上图所示，a是起点，b是环的入口，c是两个指针的第一次相遇点，ab之间的距离是x，bc之间的距离是y，从 c 点顺时针走到 b 的距离是z。则第一次相遇时，slow所走的距离是$x+y$， fast 所走的距离是 $x+(y+z)\cdot n+y$, $n$ 表示圈数，同时 fast走过的距离是 slow的两倍，也就是$2(x+y)$ ，所以我们有$x+(y+z)\cdot n+y=2(x+y)$，所以 $x=(n-1)\times (y+z)+z$。那么我们让 fast 从 c点开始走，走 x 步，会恰好走到 b点；让 slow从 a 点开始走，走 x 步，也会走到 b 点。

$$\begin{array}{rl}x+(y+z)\cdot n+y& =2(x+y)\\ x+(n+1)y+nz& =2x+2y\\ (n-1)y+nz& =x\\ (n-1)y+(n-1)z+z& =x\\ x& =(n-1)\times (y+z)+z\end{array}$$

时间复杂度

slow总共走了$2x+y$步，fast总共走了$2x+2y+x$步，所以两个指针总共走了$5x+3y$步。

从图中可以看出$y$小于等于环的长度，所以 $x+y$ 小于等于链表总长度$n$。所以总时间复杂度是 O(n)。

    func detectCycle(_ head: ListNode?) -> ListNode? {
        var fast = head
        var slow = head
      
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
            
            if fast === slow {
                slow = head
                while slow !== fast {
                    slow = slow?.next
                    fast = fast?.next
                }
                return slow
            }
        }
        return nil
    }

• 解法2——面向测试用例编程，利用val的范围，相当于将走过的节点标记了，第二次走就会被发现。

$-10^5<=Node.val<=10^5$

    func detectCycle(_ head: ListNode?) -> ListNode? {
        let maxVal = 100000
        var pointer = head
        while pointer != nil {
            if pointer?.val ?? 0 > maxVal {
                pointer?.val -= 2 * maxVal
                return pointer
            }
            pointer?.val += 2 * maxVal
            pointer = pointer?.next
        }
        return nil
    }

3.变种——判断快乐数

题目描述

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：
对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。

• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。
• 如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

---

示例 1：
输入：n = 19
输出：true
解释：
$$\begin{array}{rlrl}& 1^2+9^2=82& & \\ & 8^2+2^2=68& & \\ & 6^2+8^2=100& & \\ & 1^2+0^2+0^2=1& & \end{array}$$

---

示例 2：
输入：n = 2
输出：false
解释：
$$\begin{array}{rlrl}& 2^2=4& & \\ & 4^2=16& & \\ & 1^2+6^2=37& & \\ & 3^2+7^2=58& & \\ & 5^2+8^2=89& & \\ & 8^2+9^2=145& & \\ & 1^2+4^2+5^2=42& & \\ & 4^2+2^2=20& & \end{array}$$

解题思路

不论一个数是不是快乐数，在经历上述转换都会形成一个环，区别在于快乐数形成的环中数全为 1 ，非快乐数形成的环中数全不为 1 ，则可以用到快慢指针的方法，因为快慢指针会在环上的某处相遇，所以判断相遇处，即环中数是否为 1 ，如果为 1 则是快乐数，反之不是快乐数。

此题目的双指针并不是严格意义上的指针，而是用两个变量，fast 变量一次进行两次转换，slow 变量一次进行一次转换，两变量相等即为在环中相遇，判断相遇的数是否为 1。

快乐数19

非快乐数2

class Solution {
    func sum(_ n: Int) -> Int {
        var cnt = 0
        var num = n
        while num > 0 {
            cnt += (num % 10) * (num % 10)
            num /= 10
        }
        return cnt
    }
    
    func isHappy(_ n: Int) -> Bool {
        var slow = n
        var fast = n
        slow = sum(slow)
        fast = sum(sum(fast))
        while fast != slow {
            fast = sum(sum(fast))
            slow = sum(slow)
        }
        return slow == 1
    }
}

四、快慢指针的优势

1. 线性时间复杂度：快慢指针能够在O(n)时间内完成遍历，比暴力方法更高效。

2. 实时处理：无需额外存储大规模数据，可以在流式日志处理中使用。

3. 灵活性：可以通过调整指针步长和条件逻辑，适应多种分析需求。

五、快慢指针在实际项目中的应用

快慢指针不仅在算法竞赛中频繁出现，在实际项目开发中也有广泛应用。以下是几个应用示例：

1. 垃圾回收算法：在某些编程语言的垃圾回收算法中，快慢指针可以用于检测对象引用图中的环，帮助垃圾回收器更高效地回收内存。

2. 网络包处理：在网络编程中，快慢指针可以用于处理网络包链表，帮助快速定位特定的网络包，提高数据传输效率。

3. 日志分析：在日志分析系统中，快慢指针可以用于遍历和分析时间序列数据，帮助快速定位异常事件或特定时间点的数据。

1. 定位异常事件

• 目标：在时间序列日志中快速定位某个事件（如请求超时或错误码）。
• 方法：
  • 慢指针逐步遍历日志，记录正常事件的时间或内容。
  • 快指针跳跃式地检查是否有异常事件（如响应时间超过阈值、错误码出现等）。

logs = [(timestamp, event) for timestamp, event in log_data]
slow, fast = 0, 0
while fast < len(logs):
    if is_abnormal(logs[fast]):  # 判断是否为异常事件
        print(f"异常事件发生在时间点: {logs[fast][0]}")
    fast += 1

2. 寻找特定时间窗口的数据

• 目标：找到满足某条件的连续时间窗口（如访问量大于某阈值的窗口）。
• 方法：
  • 慢指针标记窗口起点，快指针扩展窗口。
  • 检查窗口内的数据是否符合条件。

logs = [(timestamp, value) for timestamp, value in log_data]
slow, fast = 0, 0
window_sum = 0
while fast < len(logs):
    window_sum += logs[fast][1]
    while window_sum > threshold:  # 如果窗口满足条件
        print(f"满足条件的窗口: {logs[slow][0]} 至 {logs[fast][0]}")
        window_sum -= logs[slow][1]
        slow += 1
    fast += 1

3. 查找重复事件

• 目标：检测是否有重复事件或周期性模式。
• 方法：
  • 快慢指针用于比较不同时间段的数据。
  • 如果发现两个指针指向的事件内容相同，记录下该事件。

logs = [event for timestamp, event in log_data]
slow, fast = 0, 1
while fast < len(logs):
    if logs[slow] == logs[fast]:  # 检测重复
        print(f"重复事件: {logs[slow]} 在 {slow} 和 {fast} 位置")
    slow += 1
    fast += 1

原文地址：https://blog.csdn.net/zjllll123/article/details/145304427

免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！