【刷题方法总结】快慢指针法
2019-09-29 本文已影响0人
拜仁的月饼
1. 快慢指针法方法详解
在外网中，该方法又称为“Floyd’s Cycle-Finding Algorithm”。
该方法用于判断单向链表是否有环。
该方法的执行步骤如下：
- 初始化两个指针"fast"和"slow"。
- 指针开始行动。快指针"fast"一次行两步，慢指针"slow"一次行一步。
- 如果两个指针在某点相遇，那么该链表有环；如果快指针先跑到了NULL的位置，则证明无环。
2. 代码实现及分步讲解
题目：
给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
img
示例 2：
输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。
img
示例 3：
输入：head = [1], pos = -1
输出：false
解释：链表中没有环。
img
进阶：
你能用 O(1)（即，常量）内存解决此问题吗？
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/linked-list-cycle
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
实现：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if (head == NULL) return false; // 首先确保不输入空指针。如果输入的是空指针，那么可以直接输出`false`
// 第一步：初始化两个指针
ListNode *q = head; // q: quick(fast) 快指针
ListNode *s = head; // s: slow 慢指针
// 第二步：开始走指针
while (true)
{
q = q -> next -> next; // 快的走两步
if (q == NULL) return false; // 如果q先走到了nullptr位置，那么表明无环
s = s -> next; // 慢的走一步
if(q == s) return true; // 如果两针相遇，那么证明有环
}
}
};
3. 方法正确性证明
以<u>示例1</u>为例：
img
步骤如下：
- 初始化两个指针，分别为慢指针s和快指针q，起点位于一开始的head处；
- 开始走第一步。q走到"0"位置，s走到"2"位置；
- 第二步：q走到"2"位置，s走到"0"位置；
- 第三步：q走到"4"位置，s也走到了4位置。两针相遇，证明有环。
