---
最近在刷LeetCode时,发现快慢指针在链表和查找算法中应用非常广泛,对于很多即将面试或者学习算法的同学们,熟练运用双指针也有助于对线性表更好的理解。
快慢指针,是双指针的一种应用方式。双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。基本思想是使用两个指针以不同的速度在数组或链表中移动。
换言之, 凡事需要查找的结果节点位置和链表位置相对位置明确，有属于链表节点查找问题，此方法非常有用。
快慢指针主要有三大类应用场景：
- **找到链表的中点。**
- **判断链表中是否存在环。**
- **查找或删除链表（线性表）的某个节点。**
---
## 找到链表的中点。
比如有这样一道题"如何访问链表中间节点？"
简单地实现方法:遍历一遍整个的链表，然后计算出链表的长度，进而遍历第二遍找出中间位置的数据。
如果要求只能遍历一次链表，那又当如何解决？
可以采取建立两个指针，一个指针一次遍历两个节点（快指针），另一个节点一次遍历一个节点（慢指针），当快指针遍历到空节点时，则慢指针指向的位置为链表的中间位置。
_LeetCode 876. 链表的中间结点一个带有头结点head的非空单链表，返回链表的中间结点。 若该链表有两个中间结点，则返回第二个中间结点。_
例1：输入：[1,2,3,4,5] 输出：此列表中的结点为3 (序列化形式：[3,4,5]) 返回的结点为3。 (检测系统序列化遍历该节点 [3,4,5]) 注意，我们返回了的ListNode类型的数组ans，满足： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.（意思是会最后会对结果middle以及其后的节点作校验）
例2：输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (检测系统序列化遍历该节点：[4,5,6]) 因为该列表有两个中间结点，值分别为3和4，最终返回第二个结点。
提示：链表结点数介于1到100之间。
代码如下:
```C
struct ListNode* middleNode(struct ListNode* head){
struct ListNode* pFast = head;
struct ListNode* pSlow = head;
//慢指针每次移动一步,快指针每次移动两步,直到快指针到达边界
while((pFast != NULL)&&(pFast->next != NULL))
{
pSlow = pSlow->next;
pFast = pFast->next->next;
}
return pSlow;
}
```
---
## 判断链表中是否存在环?
快指针每次遍历会比慢指针多一个元素，如果链表已经成环，无论快指针和慢指针之间相隔多少个节点，快指针总是能够追上慢指针(条件是快指针和慢指针指向同一个节点)，这个时候就可以判断链表已经成环；否则快指针进行一轮遍历之后就会跳出循环，永远不可能和慢指针“重合”。
代码如下:
``` C
bool hasCycle(struct ListNode *head) {
if (!head) return false;
struct ListNode* pFast = head;
struct ListNode* pSlow = head;
while (pFast && pFast->next)
{
pFast = pFast->next->next;
pSlow = pSlow->next;
if (pSlow == pFast)
{
return true;
}
}
return false;
}
```
---
## 删除线性表中的倒数第N个节点呢?
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
从头结点开始,快指针FIRST从N+1开始移动,慢指针SECOND指向头结点。
FIRST和SECOND相间隔N个节点，FIRST和SECOND每次移动一步。
当FIRST指向尾节点时，循环结束， SECOND的next节点即为要被删除的节点。
将SECOND的next指向被删除节点的后一个节点，即完成删除操作。
代码如下
``` C
struct ListNode* removeNthFromEnd(struct ListNode* head, int n){
if (head == NULL || head->next == NULL) return NULL;
int i;
struct ListNode* pFast = head;
struct ListNode* pSlow = head;
for (i = 0; i < n; i++)
{
pFast = pFast->next;
}
if (pFast == NULL) return head->next;
while (pFast->next)
{
pSlow = pSlow->next;
pFast = pFast->next;
}
pSlow->next = pSlow->next->next;
return head;
}
```
---
## 删除有序链表的重复元素
快慢指针还有一种应用,就是删除线性表中某些元素,在不额外增加空间复杂度的基础上(原位计算),实现数组或链表的有序化
比如给你一个字符串 S，请你删去其中的所有元音字母（ 'a'，'e'，'i'，'o'，'u'），并返回这个新字符串。
>示例 1：
输入："leetcodeisacommunityforcoders"
输出："ltcdscmmntyfrcdrs"
示例 2：
输入："aeiou"
输出：""
提示：
S 仅由小写英文字母组成。
1 <= S.length <= 1000
可以按照如下方法实现:由于字符串仅由英文字母构成,其ASCII码值从97到123构成,
1 可以构造一个128位的HASHTABLE,表中命中元音字母的元素记为1,否则为0
2 快慢指针同时从0开始，pFast一步一步向前遍历整个HASHTABLE，不受任何影响,pSlow作为输出,在只有HASHTABLE未命中时才向前走
3 将pFast的内容拷贝给pSlow,最终实现pSlow的输出。
代码如下:
``` C {.line-numbers}
char * removeVowels(char * S){
char HASH_TABLE[128] = {0};
char* pFast = S;
char* pSlow = S;
const char Vowel[] = {'a', 'e', 'i','o', 'u', '\0'};
const char* pTemp = Vowel;
while (*pTemp)
{
HASH_TABLE[*pTemp] = 1;
++pTemp;
}
while(*pFast)
{
*pSlow = *pFast;
if ( 0 == HASH_TABLE[*(pFast++)] )
{
pSlow++;
}
}
*pSlow = '\0';
return S;
}
```
---
网友评论