算法从入门到精通——双指针
上期回顾
上期我们主要介绍了
大家好，我是此生决int，欢迎来到今天的算法专题！
今天我们正式学习算法道路上的第一个经典算法——双指针算法。双 指针
为什么能把原本 O(n²) 的暴力解法优化到 O(n)？它又为什么会成为面试中的高频考点？我们接着往下看吧！
文章概要
本篇文章将从“左右指针”“快慢指针”“滑动窗口”等经典模型出发，结合 LeetCode 高频真题，带你彻底理解双指针的核心思想与解题套路。不仅会讲清楚“怎么写”，更会带你理解“为什么这样写”。
无论你是算法初学者，还是正在准备面试，都能快速建立属于自己的“双指针思维”！全程通俗易懂，包教包会，轻松拿下双指针！
双指针
本章算法题的简单总结（建议最后看）
1，数组原地操作
1，移动0，2，复写0
2，判环
3，快乐数，11，链表判环
3，单调性
3.1，左右指针指向数的特点
4，盛水最多的容器，5，有效三角形的个数
3.2，两数之和及其变式
6，两数之和，7，三数之和，8，四数之和
链表相关题目
9，中间节点，10，倒数第K节点，11，判环
1，移动0⭐️
题目链接：
解题思路：
模拟一下过程可以发现，在移动的过程中，用两个指针可以把数组分为三个区域，已经归位的——0——没有访问的,这个就是双指针算法的一个特点。
解题代码：
/* * 题目：移动零 (LeetCode 283) * 给定一个数组 nums，将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。 * 要求：必须在不复制数组的情况下原地对数组进行操作。 * * 解题思路：双指针 (快慢指针) * - dest：慢指针，指向已处理好的非零元素序列的最后一个位置（初始 -1）。 * - cur：快指针，用于遍历整个数组（初始 0）。 * - 遍历过程中： * 1. 若 nums[cur] != 0，说明遇到非零元素，需要将其交换到前面。 * 先将 dest 后移一位 (++dest)，然后交换 nums[cur] 与 nums[dest]， * 最后 cur 后移一位 (cur++)。 * 2. 若 nums[cur] == 0，则不做交换，只将 cur 后移一位，跳过该零元素。 * - 整个过程保证了非零元素的相对顺序，且所有零被“挤”到数组末尾。 * - 时间复杂度 O(n)，空间复杂度 O(1)。 */ class Solution { public: void moveZeroes(vector<int>& nums) { int dest = -1; // 慢指针，指向已处理好的非零序列末尾 int cur = 0; // 快指针，用于扫描数组 while (cur < nums.size()) { if (nums[cur] != 0) { // 当前元素非零：dest向前移动，然后与cur交换，将非零元素归位 swap(nums[cur++], nums[++dest]); } else { // 当前元素为零：仅移动快指针，跳过 cur++; } } } };
2，复写0⭐️⭐️
题目链接：
解题思路：
首先我们想到就是新建一个数组来存储模拟，但是这里要求必须在原数组上修改，所以不能创建新的数组，然后，有人从前向后模拟会发现会改变数组原来的值，又不行！再试试从后向前完成复写，我们发现我们要先找到要复写的最后一个复写的数！！
解题代码1：
/* * 题目：复写零 (LeetCode 1089) * 给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍， * 并将其余的元素向右平移。注意：不要超过数组长度写入元素，必须原地修改。 * * 解题思路：两次遍历，双指针（快慢指针模拟 + 反向填充） * 1. 第一次遍历（模拟复写）： * - slow 指针逐个扫描原数组元素，fast 指针模拟在结果数组中的下标。 * - 当 fast < n 时，若 arr[slow] == 0，fast 前进两步（复写两个零）， * 否则 fast 前进一步；同时 slow 前进一步。 * - 循环结束后，slow 指向原数组中最后一个会被保留的元素之后的位置。 * 2. 边界处理： * - 如果 fast == n+1，说明原数组中最后一个零在复写时会超出数组右边界， * 只能保留一个零。此时将数组最后一个元素直接置为 0， * 并回退指针：fast 指向 n-1，slow 回退一位。 * 3. 第二次遍历（从后向前原地填充）： * - 利用 slow 从后向前遍历原数组，fast 从结果数组末尾向前填充。 * - 若 arr[slow-1] == 0，则在 arr[fast-1] 和 arr[fast-2] 处放两个 0， * fast 减 2，slow 减 1。 * - 否则将 arr[slow-1] 复制到 arr[fast-1]，fast 和 slow 各减 1。 * - 从后向前操作保证了未处理的元素不会被覆盖。 * - 时间复杂度 O(n)，空间复杂度 O(1)。 */ class Solution { public: void duplicateZeros(vector<int>& arr) { int n = arr.size(); int fast = 0; // 快指针，模拟复写零后在结果数组中的下标 int slow = 0; // 慢指针，遍历原数组 // 第一遍：模拟复写，找到原数组中最后一个会被保留的元素 while (fast < n) { if (arr[slow] == 0) { fast += 2; // 遇到0，结果中会放两个0，快指针前进两步 } else { fast += 1; // 非0元素，结果中放一个，快指针前进一步 } slow++; // 原数组指针前进一步 } // 边界情况：模拟结束后 fast == n+1，说明最后的0复写会越界一个位置 if (fast == n + 1) { arr[n - 1] = 0; // 数组最后一个元素强制置0（只能放下一个0） fast = n - 1; // 修正 fast 指针到最后一个有效下标 slow--; // slow 回退，跳过这个导致越界的0 } // 第二遍：从后向前填充，避免覆盖未处理的元素 while (slow > 0) { if (arr[slow - 1] == 0) { // 原数组中是0，结果中连续放两个0 arr[fast - 1] = 0; arr[fast - 2] = 0; fast -= 2; // 填充了两个位置 } else { // 非0元素直接复制 arr[fast - 1] = arr[slow - 1]; fast -= 1; // 填充了一个位置 } slow--; // 原数组指针前移 } } };
没懂？看看下面的大神代码！！
大神解题代码
void duplicateZeros(vector<int>& arr) { // 1. 先找到最后一个数 int cur = 0, dest = -1, n = arr.size(); while(cur < n) { if(arr[cur]) dest++; else dest += 2; if(dest >= n - 1) break; cur++; } // 2. 处理一下边界情况 if(dest == n) { arr[n - 1] = 0; cur--; dest -=2; } // 3. 从后向前完成复写操作 while(cur >= 0) { if(arr[cur]) arr[dest--] = arr[cur--]; else { arr[dest--] = 0; arr[dest--] = 0; cur--; } } }
代码分析：
主流程步骤：
先判断 cur 位置的值
决定 dest 向后移动一步或者两步
判断一下 dest 是否已经到结束为止
cur++
补充步骤：
1.5 处理一下边界情况
3，快乐数⭐️⭐️⭐️
题目链接：
解题思路：
乍一看没有任何思路，但不管是通过模拟还是自己发现，假设一个很大的数，10位，每位上全是9，但他经过一次变换后最大也就是1099，一下就变小了，也就是说，最终会坍缩在一个很小的范围里面。那我们要怎么判断一个数不是快乐数呢？没错，就是进入了循环！（题目也说了，要么变成1，要么有循环）
那么我们要怎么判断他是不是有环呢？那就是双指针！！也叫快慢指针（常用！！！）
解题代码1：
/* * 题目：快乐数 (LeetCode 202) * 编写一个算法判断一个数 n 是不是快乐数。 * 快乐数定义：每次将数字替换为其各位数字的平方和，重复这个过程， * 如果最终能得到 1，则是快乐数；如果陷入无限循环且始终得不到 1，则不是。 * * 解题思路：快慢指针 (Floyd 判圈算法) * - 由于求平方和的过程要么最终到 1，要么进入一个不包含 1 的循环。 * 问题转化为检测链表中是否存在环（且环点是否为 1）。 * - 使用两个指针 slow 和 fast，初始都指向 n。 * - slow 每次走一步（调用一次 change） * - fast 每次走两步（调用两次 change） * - 如果过程中任一指针达到 1，说明是快乐数，返回 true。 * - 如果快慢指针相遇（相等）且值不为 1，说明进入了无 1 的循环，返回 false。 * - 时间复杂度 O(log n) 量级，空间复杂度 O(1)。 */ class Solution { // 辅助函数：计算一个数各位数字的平方和 int change(int n) { int ret = 0; while (n) { int x = n % 10; // 取出最后一位 ret += (x * x); // 累加平方 n /= 10; // 去掉最后一位 } return ret; } public: bool isHappy(int n) { int fast = n; // 快指针，每次走两步 int slow = n; // 慢指针，每次走一步 while (true) { // 途中任一指针到达 1，说明是快乐数 if (fast == 1 || slow == 1) return true; // 快指针移动两步 fast = change(fast); fast = change(fast); // 慢指针移动一步 slow = change(slow); // 若两指针相遇且不为 1，说明进入了无限循环且不是快乐数 if (fast == slow && fast != 1) return false; } } };
没懂？看看大神的代码！！
大神解题代码
// 解题思路： // 快乐数的判定存在两种情况：最终变为1，或进入不含1的无限循环 // 采用快慢指针法（龟兔赛跑）检测循环：慢指针每次计算1次平方和，快指针每次计算2次 // 若两指针相遇时值为1，则是快乐数；否则说明陷入循环，不是快乐数 class Solution { public: // 计算数字n每一位的平方和 int bitSum(int n) { int sum = 0; while(n) // 循环提取每一位数字 { int t = n % 10; // 取当前个位数字 sum += t * t; // 累加平方和 n /= 10; // 去掉个位，处理下一位 } return sum; } bool isHappy(int n) { // 初始化快慢指针：慢指针从n开始，快指针先走一步（避免初始状态相等） int slow = n, fast = bitSum(n); // 循环直到快慢指针相遇（检测循环） while(slow != fast) { slow = bitSum(slow); // 慢指针：每次走1步（计算1次平方和） fast = bitSum(bitSum(fast)); // 快指针：每次走2步（计算2次平方和） } // 相遇时的值为1，说明是快乐数；否则说明陷入非1循环 return slow == 1; } };
4，盛水最多的容器⭐️⭐️⭐️
题目链接：
解题思路：
1，暴力
枚举左右两个边，每次都算出可以成的水，
2，双指针
我们先模拟一下会发现
这就是这道题的特性。
解题代码
这边建议直接看后面大神的代码
/* * 解题思路：对撞双指针 + 贪心跳过无效状态 * - 初始时，左右指针分别指向数组两端，计算当前容水量。 * - 每次移动较短的那一侧指针，并跳过所有高度不超过该侧原高度的柱子， * 因为宽度减小的情况下高度不增，面积必然不会更大，可以直接排除。 * - 移动后重新计算面积，更新最大值，直至两指针相遇。 * - 时间复杂度 O(n)，空间复杂度 O(1)。 */ class Solution { public: int maxArea(vector<int>& height) { int l = 0, r = height.size() - 1; // 左右指针 int h = min(height[l], height[r]); // 当前短板高度 int ret = h * (r - l); // 初始面积 while (l < r) { if (height[l] < height[r]) { // 左边为短板，尝试右移左指针 int ll = l + 1; // 跳过所有高度不大于原左边高度的柱子 while (height[ll] < height[l] && ll < r) { ll++; } l = ll; // 更新左指针 int v = (r - l) * min(height[l], height[r]); ret = max(v, ret); } else { // 右边为短板（或等高），尝试左移右指针 int rr = r - 1; // 跳过所有高度不大于原右边高度的柱子 while (height[rr] < height[r] && rr > l) { rr--; } r = rr; // 更新右指针 int v = (r - l) * min(height[l], height[r]); ret = max(v, ret); } } return ret; } };
没懂？看看大神的解题代码！！
大神解题代码
class Solution { public: int maxArea(vector<int>& height) { // 初始化左右指针（分别指向数组两端）、记录最大水量ret int left = 0, right = height.size() - 1, ret = 0; // 双指针未相遇时循环 while(left < right) { // 计算当前容器水量：较短边高度 × 两指针距离 int v = min(height[left], height[right]) * (right - left); // 更新最大水量 ret = max(ret, v); // 移动指针：只移动较短边，才有可能找到更大水量 if(height[left] < height[right]) left++; // 左边更短，左指针右移 else right--; // 右边更短或相等，右指针左移 } return ret; // 返回最大水量 } };
5，有效三角形个数⭐️⭐️⭐️
题目链接：
解题思路：
因为有三条边，我们可以先固定一条边，首先，我们要要知道三角形的条件，任意两边之和大于第三边，即两条边大于最大的边即可。我们要先对数组排序，然后，我们先固定最大的一条边，大小为C，那么，
对于区间【0，C-1】（令【a,b】）里面，
如果两 边界
之和a+b大于C，那么，a之后的所有边与b组合都比C大，所以直接算出这个区间的三角形个数为b-a个，区间更新位【a，b-1】
如果两边界之和a+b小于C，那么，b之前的所有边与a组合都比C小，所以，区间更新为【a+1,b】
解题代码
/* * 解题思路：排序 + 双指针（固定最长边） * - 首先将数组排序，方便判断三边关系。 * - 固定最长的边 nums[j]（j 从末尾向前遍历）， * 在 [0, j-1] 区间使用对撞双指针 l, r 寻找两条“短边” * 满足 nums[l] + nums[r] > nums[j]。 * - 若满足，则 l 到 r-1 之间的所有元素都能与 r 和 j 组成三角形， * 累加 (r - l) 并右指针左移；否则左指针右移。 * - 时间复杂度 O(n²)，空间复杂度 O(1)。 */ class Solution { public: int triangleNumber(vector<int>& nums) { int l = 0, r = nums.size(); // 预定义双指针（实际会在循环内重置） int ret = 0; sort(nums.begin(), nums.end()); // 排序，使数组单调递增 // 固定最长边 j（至少要有两条更短的边，故 j >= 2） for (int j = nums.size() - 1; j >= 2; j--) { l = 0; r = j - 1; // 双指针置于当前最长边的左侧区间 while (l < r) { // 两短边之和大于最长边，可组成三角形 if (nums[l] + nums[r] > nums[j]) { ret += (r - l); // 从 l 到 r-1 的所有元素都与 r 和 j 满足条件 r--; // 尝试更小的右指针对应值 } else { l++; // 和太小，左指针右移增大 sum } } } return ret; } };
没懂？看看大神的解题代码！！
大神解题代码
int triangleNumber(vector<int>& nums) { // 1. 对数组升序排序，方便利用三角形三边关系的特性 sort(nums.begin(), nums.end()); // 2. 初始化结果计数器，n 为数组长度 int ret = 0, n = nums.size(); // 从后往前固定最大边 nums[i]，i 至少为 2 才能凑齐三元组 for(int i = n - 1; i >= 2; i--) { // 双指针：left 指向区间左端，right 指向区间右端（最大边的前一个位置） int left = 0, right = i - 1; while(left < right) { // 若较小两边之和 > 最大边，说明 [left, right-1] 与 right 组成的三元组都有效 if(nums[left] + nums[right] > nums[i]) { ret += right - left; // 累加当前 right 对应的所有有效组合数 right--; // 右指针左移，尝试更小的 right } else { // 和不够大，左指针右移，增大较小边的和 left++; } } } return ret; }
6，两数之和——查找总价格为目标值的两个商品⭐️
题目链接：
解题思路：
有了上面三角形的那个题的思路，我们可以定义两个指针left和right，如果两区间端点的值大于target，right–；小于left++；
解题代码
/* * 解题思路：排序 + 双指针（固定最长边） * - 首先将数组排序，方便判断三边关系。 * - 固定最长的边 nums[j]（j 从末尾向前遍历）， * 在 [0, j-1] 区间使用对撞双指针 l, r 寻找两条“短边” * 满足 nums[l] + nums[r] > nums[j]。 * - 若满足，则 l 到 r-1 之间的所有元素都能与 r 和 j 组成三角形， * 累加 (r - l) 并右指针左移；否则左指针右移。 * - 时间复杂度 O(n²)，空间复杂度 O(1)。 */ class Solution { public: int triangleNumber(vector<int>& nums) { int l = 0, r = nums.size(); // 预定义双指针（实际会在循环内重置） int ret = 0; sort(nums.begin(), nums.end()); // 排序，使数组单调递增 // 固定最长边 j（至少要有两条更短的边，故 j >= 2） for (int j = nums.size() - 1; j >= 2; j--) { l = 0; r = j - 1; // 双指针置于当前最长边的左侧区间 while (l < r) { // 两短边之和大于最长边，可组成三角形 if (nums[l] + nums[r] > nums[j]) { ret += (r - l); // 从 l 到 r-1 的所有元素都与 r 和 j 满足条件 r--; // 尝试更小的右指针对应值 } else { l++; // 和太小，左指针右移增大 sum } } } return ret; } };
没懂？看看大神的解题代码！！
大神解题代码
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { // 初始化双指针：左指针指向数组开头，右指针指向数组末尾 int left = 0, right = nums.size() - 1; // 双指针未相遇时循环查找 while(left < right) { // 计算当前两数之和 int sum = nums[left] + nums[right]; if(sum > target) right--; // 和过大，右指针左移，减小和 else if(sum < target) left++; // 和过小，左指针右移，增大和 else return {nums[left], nums[right]}; // 和等于目标值，直接返回 } // 照顾编译器语法（实际题目保证有解，此分支不会执行） return {-4941, -1}; } };
7，三数之和⭐️⭐️（会了前面之后）
题目链接：
解题思路：
类 似三角形那题，先固定一个数，再在那个区间里面使用双指针，注意，这题要去重（关键），
解题代码
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(),nums.end()); vector<vector<int>> ret; for(int i=nums.size()-1;i>=2;) { if(nums[i]<0) break; int left=0; int right=i-1; while(left<right) { if(nums[left]+nums[right]+nums[i]>0) { right--; } else if(nums[left]+nums[right]+nums[i]<0) { left++; } else { vector<int>tmp; tmp.push_back(nums[left]); tmp.push_back(nums[right]); tmp.push_back(nums[i]); ret.push_back(tmp); left++; right--; while(nums[right]==nums[right+1]&&right>left) { right--; } while(nums[left]==nums[left-1]&&left<right) { left++; } } } i--; while(nums[i]==nums[i+1]&&i>=2)i--; } //o（N*N） return ret; } };
没懂？看看大神的解题代码！！
大神解题代码
#include <vector> #include <algorithm> using namespace std; class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ret; // 1. 对数组升序排序，方便双指针操作和去重 sort(nums.begin(), nums.end()); int n = nums.size(); // 2. 固定第一个数 nums[i]，遍历所有可能的i for(int i = 0; i < n; ) { // 优化：nums[i] > 0时，后续数均非负，三数之和不可能为0，直接break if(nums[i] > 0) break; int left = i + 1; // 左指针：从i的下一个位置开始 int right = n - 1; // 右指针：从数组末尾开始 int target = -nums[i]; // 目标和：需找到两数之和等于 -nums[i] while(left < right) { int sum = nums[left] + nums[right]; if(sum > target) right--; // 和大于目标，右指针左移，减小和 else if(sum < target) left++; // 和小于目标，左指针右移，增大和 else { // 找到一组和为0的三元组，加入结果集 ret.push_back({nums[i], nums[left], nums[right]}); left++; right--; // 对left去重：跳过与前一个值相同的数 while(left < right && nums[left] == nums[left - 1]) left++; // 对right去重：跳过与后一个值相同的数 while(left < right && nums[right] == nums[right + 1]) right--; } } // 对i去重：跳过与前一个值相同的数，避免重复三元组 i++; while(i < n && nums[i] == nums[i - 1]) i++; } return ret; } };
8，四数之和⭐️⭐️（会了前面之后）
题目链接：
四数之和
在这里插入图片描述
解题思路：
就是三数之和的变式，先固定两个数，再用双指针即可。不会的建议先学会三数之和。
解题代码
/* * 解题思路：排序 + 固定前两个数 + 双指针 * - 首先将数组排序，便于后续去重和双指针查找。 * - 第一层循环固定第一个数 nums[i]，第二层循环固定第二个数 nums[j]。 * - 在剩余子数组 [j+1, n-1] 上使用对撞双指针 left 和 right， * 寻找与 nums[i]+nums[j] 相加等于 target 的剩下两个数。 * - 根据四数之和与 target 的关系移动左右指针，找到解后记录， * 同时跳过重复元素避免结果集重复。 * - 每一层固定数移动时也跳过重复值，保证最终四元组不重复。 * - 时间复杂度 O(n³)，空间复杂度 O(1)（不计返回结果）。 */ class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); // 排序 int n = nums.size(); vector<vector<int>> ret; int i = 0, j = 0; // 第一层：固定第一个数 for (i = 0; i < n - 3;) { // 第二层：固定第二个数 for (j = i + 1; j < n - 2;) { // 剪枝：当前最小两数和已 >= target，后续只会更大 if (nums[i] + nums[j] >= target) break; int left = j + 1; // 左指针 int right = n - 1; // 右指针 while (left < right) { int sum = nums[left] + nums[right] + nums[i] + nums[j]; if (sum > target) { right--; // 和偏大，右指针左移 } else if (sum < target) { left++; // 和偏小，左指针右移 } else { // 找到一组解，记录 ret.push_back({nums[i], nums[j], nums[left], nums[right]}); right--; left++; // 跳过左指针重复元素 while (left < right && nums[left] == nums[left - 1]) left++; // 跳过右指针重复元素 while (left < right && nums[right] == nums[right + 1]) right++; } } j++; // 跳过重复的第二个数 while (j < n - 2 && nums[j] == nums[j - 1]) j++; } i++; // 跳过重复的第一个数 while (i < n - 3 && nums[i] == nums[i - 1]) i++; } return ret; } };
没懂？看看大神的解题代码！！
大神解题代码
和我的一样
链表相关的双指针题（中点，判环，倒K）
**这些代码这里就没有解析咯！**要看解析可以去看题解或我的链表那期博文哦！！
9，链表的中间节点
题目链接：链表的中间节点
解题代码：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ typedef struct ListNode listnode; class Solution { public: ListNode* middleNode(ListNode* head) { // 快慢指针法：快指针速度是慢指针的2倍，快指针到尾时慢指针刚好在中间 listnode* fast = head; // 快指针：每次走2步 listnode* slow = head; // 慢指针：每次走1步 // 循环条件：fast和fast->next不为空，避免访问空指针，兼容奇偶长度链表 while (fast && fast->next) { slow = slow->next; // 慢指针走1步 fast = fast->next; // 快指针先走第1步 if (fast) fast = fast->next;// 快指针再走第2步（凑够2步，避免空指针） } return slow; // 循环结束时，slow指向中间结点（偶数长度时返回第二个中间结点） } };
10，倒数第K个节点
题目链接：
返回链表倒数第K个节点
解题代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ typedef struct ListNode listnode; class Solution { public: ListNode* middleNode(ListNode* head) { // 快慢指针法：快指针速度是慢指针的2倍，快指针到尾时慢指针刚好在中间 listnode* fast = head; // 快指针：每次走2步 listnode* slow = head; // 慢指针：每次走1步 // 循环条件：fast和fast->next不为空，避免访问空指针，兼容奇偶长度链表 while (fast && fast->next) { slow = slow->next; // 慢指针走1步 fast = fast->next; // 快指针先走第1步 if (fast) fast = fast->next;// 快指针再走第2步（凑够2步，避免空指针） } return slow; // 循环结束时，slow指向中间结点（偶数长度时返回第二个中间结点） } };
解题代码：
11，判环
题目链接：
判断链表是否有环
解题代码
/** * 解题思路：快慢指针法（Floyd 判圈算法） * - 定义两个指针：慢指针每次走一步，快指针每次走两步。 * - 若链表无环，快指针会先到达 nullptr，返回 false。 * - 若链表有环，快慢指针最终会在环内相遇，返回 true。 * - 特殊情况：空链表或只有一个节点且无环的直接返回 false。 * * 时间复杂度 O(n)，空间复杂度 O(1) */ /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { typedef struct ListNode listnode; public: bool hasCycle(ListNode *head) { // 空链表一定无环 if (head == NULL) return false; // 只有一个节点且没有自环（next为NULL），无环 if (head->next == NULL) return false; // 快慢指针初始化都指向头节点 listnode *fast = head; listnode *slow = head; // 当快慢指针均非空时继续移动 while (fast && slow) { slow = slow->next; // 慢指针走一步 fast = fast->next; // 快指针先走一步 if (fast) // 如果快指针未到末尾，再走一步（共两步） fast = fast->next; // 快慢指针相遇说明存在环 if (fast == slow) return true; } // 遍历结束未相遇，无环 return false; } };
双指针算法本质剖析
双指针 = 用两个位置之间的关系，减少重复遍历。不再“穷举所有情况”，而是“边移动边排除”。一般可以将O（N*N）的时间复杂度优化为O(N)。双指针的核心本质，双指针是在“利用单调性”“来排除一大片不可能情况”
什么时候适合用双指针
1. 数组有序
两数之和
三数之和（四数之和）
2. 涉及“连续区间”（目前还没有找到合适的题目）
最长子串
最短子数组
连续和
3. 需要原地操作
删除元素
移动零
数组去重
4. 链表问题
找中点
判断环
倒数第 k 个节点
题型总结
双指针的题目主要可以分为以下几个类型
1. 左右夹逼型（左右指针）
适用于：
1，有序数组
2，回文判断
3，两数之和
比如我们上面的 1，2，4，5，6，7，8
2. 快慢指针
适用于：
1，链表相关的（中点，判环，倒K）
2，去重和删除元素
3，判环
比如我们上面的 3
3. 滑动窗口
在下期啦！！！
下期预告
双指针的变式——滑动窗口！！！
结语
本期内容就到这里啦，欢迎大家在评论区一起交流讨论
如果你也在为蓝桥杯/ACM备赛头疼，或是准备算法面试找不到系统学习路径，欢迎订阅我的「算法从入门到精通」专栏！
这里没有枯燥的理论堆砌，只有完整的算法学习路线，
搭配精选梯度习题+清晰思路解析，帮你把每个算法学透、练熟。包教包会的！
我们一起在算法路上稳步进阶！
