[TOC]

# 双指针

## 概述

双指针的核心是使用两个指针同向或相向移动，从而高效的遍历数组或链表等线性数据结构；

这里指针并不是指 `C++` 里的指针类型，而是指有指针作用可以指向某个下标或元素的变量；

使用双指针通常需要确定移动的条件和方向（部分题还会需要确定移动的步长）；

### 优势

1. **时间复杂度低**：双指针算法通常可以在`O(n)`的时间复杂度内解决问题，避免了嵌套循环带来的高时间复杂度。
2. **空间复杂度低**：双指针算法不需要额外的数据结构存储中间结果，空间复杂度通常为`O(1)`。



## 应用场景

### 同向双指针

> [21. 合并两个有序链表](https://leetcode.cn/problems/merge-two-sorted-lists/)

![image-20250201120708863.png](https://pic.leetcode.cn/1738424241-ITGzKv-image-20250201120708863.png)

这两个指针：

- 移动条件：指向的值更小的指针移动；
- 移动方向：同向；
- 移动速度：都是1个单位；

### 相向双指针

> [344. 反转字符串](https://leetcode.cn/problems/reverse-string/)

![image-20250131192102867.png](https://pic.leetcode.cn/1738424235-AlCEzH-image-20250131192102867.png)

这里左右指针：

- 移动条件：每次交换字符后，都移动；
- 移动方向：相向；
- 移动速度：都是1个单位；

### 快慢指针

> [141. 环形链表](https://leetcode.cn/problems/linked-list-cycle/)

![image-20250201224117584.png](https://pic.leetcode.cn/1738424258-vTSMTL-image-20250201224117584.png)


这里双指针：

- 移动条件：每次都移动，直到有一个指针遍历到空节点，或者两个指针相遇；
- 移动方向：相向；
- 移动速度：快指针2个单位，慢指针1个单位；

学习分享

双指针 概述 优势 应用场景 同向双指针 相向双指针 快慢指针
 双指针
 概述
双指针的核心是使用两个指针同向或相向移动，从而高效的遍历数组或链表等线性数据结构；
这里指针并不是指 C++ 里的指针类型，而是指有指针作用可以指向某个下标或元素的变量；
使用双指针通常需要确定移动的条件和方向（部分题还会需要确定移动的