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

我们遍历一个数组，并输出数组每一项，我们需要一个指针来记录当前遍历的项，这个指针我们可以叫单指针（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-