c语言使用指针的基本原则：双指针之快慢指针

c语言使用指针的基本原则：双指针之快慢指针// 快慢指针 L = 0 R = 0 while 没有遍历完 if 一定条件 L = 1 R = 1 return 合适的值典型实例：步长不等的快慢指针是指针使用两个步长不同的指针，通常快指针用于读，慢指针用于写。I 步长不等的快慢指针（两个指针步长不同），如用来排除重复元素。II 左右端点指针（两个指针分别指向头尾，并往中间移动，步长不确定），如实现二分查找。III 步长相等的快慢指针（两个指针间距相同，步长相同），如一次遍历（OnePass）求链表的中点或求单链表的倒数第k个元素。

遍历是实现许多算法的基本操作。遍历数据或链表通常通过指针（或索引）在循环内实现指针的移动来进行。

我们遍历一个数组，并输出数组每一项，我们需要一个指针来记录当前遍历的项，这个指针我们可以叫单指针（index）。在某些情况下，可能使用两个这样的指针来遍历更方便问题求解，称为双指针。

伪代码：

// 单指针 for(int i = 0;i < nums.size(); i ) { 输出(nums[i]); } // 双指针 int L = 0; int R = nums.size() - 1; while (L < R) { if(一定条件) return 合适的值，一般是 L 和 R 的中点 if(一定条件) L if(一定条件) R-- } // 因为 L == R 因此返回 I 和 R 都是一样的 return L

双指针是指对数据结构（如数组和链表）使用两个指针或两个索引来操作数据，其策略一般有：

I 步长不等的快慢指针（两个指针步长不同），如用来排除重复元素。

II 左右端点指针（两个指针分别指向头尾，并往中间移动，步长不确定），如实现二分查找。

III 步长相等的快慢指针（两个指针间距相同，步长相同），如一次遍历（OnePass）求链表的中点或求单链表的倒数第k个元素。

1 步长不等的快慢指针

步长不等的快慢指针是指针使用两个步长不同的指针，通常快指针用于读，慢指针用于写。

// 快慢指针 L = 0 R = 0 while 没有遍历完 if 一定条件 L = 1 R = 1 return 合适的值

典型实例：

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1：

给定 int nums[] = {1 1 1 2 2 3};

函数应返回新长度 length = 5 并且原数组的前五个元素被修改为 1 1 2 2 3 。

你不需要考虑数组中超出新长度后面的元素。

示例 2：

给定 int nums[] = {0 0 1 1 1 1 2 3 3};

函数应返回新长度 length = 7 并且原数组的前五个元素被修改为 0 0 1 1 2 3 3 。

你不需要考虑数组中超出新长度后面的元素。

实际上这种问题可以更抽象一步，即“删除排序数组中的重复项，使得相同数字最多出现 k 次” 。 那么这道题 k 就是 2，如果 k 为 1，则是删除重复元素。。

• 初始化快慢指针 slow ， fast ，全部指向索引为 0 的元素。
• fast 每次移动一格
• 慢指针选择性移动，即只有写入数据之后才移动。是否写入数据取决于 slow - 2 对应的数字和 fast 对应的数字是否一致。
• 如果一致，我们不应该写。 否则我们就得到了三个相同的数字，不符合题意。
• 如果不一致，我们需要将 fast 指针的数据写入到 slow 指针。
• 重复这个过程，直到 fast 走到头，说明我们已无数字可写。

图解（红色的两个数字，表示我们需要比较的两个数字）：

code:

#include <stdio.h> // 快慢指针（读写指针） #include <vector> using namespace std; class Solution { public: int removeDuplicates(vector<int>& nums int k) { int i = 0; for(int j=0;j<nums.size();j ) if (i < k || nums[j] != nums[i - k]) { nums[i] = nums[j]; i ; } return i; } }; template <typename TT> void print(TT tt int n) { for(int i=0;i<n;i ) printf("%d " tt[i]); printf("\n"); } int main() { int nums[] = {0 0 1 1 1 1 2 3 3}; int size = sizeof nums / sizeof *nums; vector<int> vc(nums nums size); Solution st; int n = st.removeDuplicates(vc 2); print(nums size); print(vc n); vector<int> vc2(nums nums size); n = st.removeDuplicates(vc2 1); print(vc2 n); getchar(); return 0; } /* 0 0 1 1 1 1 2 3 3 0 0 1 1 2 3 3 0 1 2 3 */2 左右端点指针

两个指针分别指向头尾，并往中间移动，步长不确定。

// 左右端点指针 L = 0 R = n - 1 while L < R if 找到了 return 找到的值 if 一定条件1 L = 1 else if 一定条件2 R -= 1 return 没找到

典型实例：二分查找：

先定义搜索区间（非常重要）

根据搜索区间定义循环结束条件

取中间元素和目标元素做对比（目标元素可能是需要找的元素或者是数组第一个，最后一个元素等）（非常重要）

根据比较的结果收缩区间，舍弃非法解（也就是二分）

如果是整体有序通常只需要nums[mid]和target比较即可。如果是局部有序，则可能需要与其周围的特定元素进行比较。

code:

#include <stdio.h> #include <vector> using namespace std; int binarySearch(vector<int>& nums int target){ if(nums.size() == 0) return -1; int left = 0 right = nums.size() - 1; while(left <= right){ int mid = left ((right - left) >> 1); if(nums[mid] == target){ return mid; } // 搜索区间变为 [mid 1 right] else if(nums[mid] < target) left = mid 1; // 搜索区间变为 [left mid - 1] else right = mid - 1; } return -1; } int main() { int arr[] = {1 2 3 4 5 6 7}; vector<int> vc(arr arr 7); printf("%d\n" binarySearch(vc 5)); getchar(); return 0; }

回文验证：

#include <stdio.h> #include <string> using namespace std; bool isPalindrome(string s) { if (s.empty()) return true; const char* left = s.c_str(); const char* end = left s.length() - 1; while (end > left) { if (!isalnum(*left)) { left; continue;} if (!isalnum(*end)) {--end; continue;} if (tolower(*left) != tolower(*end)) return false; else {--end; left;} } return true; } int main() { string s = "20122102"; string t = "abcabc"; printf("%d %d\n" isPalindrome(s) isPalindrome(t)); getchar(); return 0; }3 步长相等的快慢指针

两个指针步长相同。

// 步长相等的快慢指针 L = 0 R = k while没有遍历完 自定义逻辑 L = 1 R = 1 return 合适的值

典型实例：利用固定间距指针寻找链表中点

利用两个指针fast、slow同时指向头节点，fast指针每次走两步，slow指针每次走一步，当fast指针到达链表尽头时，slow指针就处于链表中点处。

Node* middle(Node* head) { Node* fast *slow; fast = slow = head; while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; } return slow; //slow即在中间位置 }

如果链表长度是奇数时，此时slow 正好为中点，如果为偶数，那么slow位置是中间偏右。

典型实例：一次遍历（OnePass）求单链表的倒数第k个元素：

#include<stdio.h> // 一次遍历（OnePass）求单链表的倒数第k个元素 #include<stdlib.h> typedef struct Node { int num; Node *next; }Linklist; Linklist * creat_linklist(); //尾插法创建含有头结点的单链表 int Search_K(Linklist *h int k) //双指针算法查找节点 { Linklist *fast = h->next; Linklist *slow = h->next; int count = 0; // 计数器 while(fast!=NULL) { fast = fast->next; if(count < k) count ; else slow = slow->next; } if(count < k) //如果K大于链表的长度情况 { printf("您要查找的节点不存在！"); return 0; } else { printf("倒数第%d个节点的数据为：%d\n" k slow->num); printf("*** 查找完成！***"); return 1; } } Node* middle(Node* head) { Node* fast *slow; fast = slow = head; while (fast != NULL && fast->next != NULL) { fast = fast->next->next; slow = slow->next; } return slow; //slow即在中间位置 } void print(Linklist* head) { while(head->next != NULL) { printf("%d " head->next->num); head = head->next; } printf("%\n"); } int main() { int k; Linklist *head; head = (Linklist *)malloc(sizeof(Linklist)); head = creat_linklist(); print(head); printf("中间节点是：%d\n" *middle(head)); printf("请输入要查找的倒数第几个节点："); scanf("%d" &k); Search_K(head k); while(1); return 0; } Linklist * creat_linklist() { int n=0 t=1; Linklist *h *p *q; h = q =(Linklist *)malloc(sizeof(Linklist)); for(int i=0;i<100;i ) { p = (Linklist *)malloc(sizeof(Linklist)); p->num = i 1; q->next = p; q = p; } q->next = NULL; return h; }

在一些场合还需要考虑使用三个指针，如链表逆转：

ListNode* reverseList(ListNode* head) { ListNode* prev = NULL; ListNode* cur = head; ListNode* next = NULL; while(cur != NULL) { next = cur->next; cur->next = prev; prev = cur; cur = next; } return prev; }

ref:

https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/91/two-pointers

-End-