雙指標一般運用于陣列和鏈表當中，在陣列當中，我們通常利用2個下標去進行操作(如:洗掉陣列中的某個元素，二分查找等)；在鏈表當中，我們會去用2個指標(快指標fast和慢指標slow)對鏈表結構進行操作(如:求鏈表的中間結點，求相交鏈表的交點，判斷鏈表是否成環等)，

雙指標在陣列中的應用：

1.原地洗掉陣列中值為val的元素，要求時間復雜度為O(N)，空間復雜度為O(1)

這道題由于時間復雜度的限制，沒辦法用雙重回圈去洗掉陣列中的重復元素，因此這里采用了雙下標去洗掉的做法，一個下標為slow，另一個為fast，它們都從0開始，當某位置的元素不是val，將fast下標的值賦值給slow后，fast和slow一起++；如果某位置的元素是val，則slow不進行任何操作，fast++，當fast = 陣列大小 -1的時候結束回圈，

int removeElement(int* nums, int numsSize, int val)
{
    //定義2個下標變數
    int slow = 0;
    int fast = 0;
    while(fast < numsSize)
    {
        //判斷是否是要洗掉的元素
        if(nums[fast] == val)
        {
            fast++;
        }
        else
        {
            nums[slow] = nums[fast];
            fast++;
            slow++;
        }
    }
    //回傳洗掉后的元素個數
    return slow;
}

2.逆置陣列(反轉陣列)

定義2個下標left和right，left從0開始，right從陣列的大小-1開始，2個下標所對應的元素進行交換，最終當left >= right的時候停止交換，

void reverse(int* nums, int size) 
{
    int left = 0;
    int right = size - 1;
    while (left < right) 
    {
        //交換left和right對應的元素
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
        left++;
        right--;
    }
}

雙指標在鏈表中的應用:

1.求鏈表的中間結點(如果有2個中間結點，回傳第2個)

定義快指標fast和慢指標slow，fast每次走2步，slow每次走1步，這樣當fast到尾結點或者NULL的時候，slow正好處于鏈表的中間位置，

下圖是對應2種情況，fast->next為NULL和fast為NULL，

struct ListNode* middleNode(struct ListNode* head)
{
    //定義2個指標，快指標1次走2格，慢指標1次走1格
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    //注意判斷條件，fast為NULL時fast在NULL處，fast->next=NULL時fast在尾結點處，
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

2.求鏈表的倒數第k個結點

定義快指標fast和慢指標slow，要求倒數第k個結點，也就是這個結點是距離尾結點的距離為k-1【距離NULL為k】，此時讓fast指標先走k步，然后fast和slow一起走，當fast==NULL時候，slow所指向的結點就是倒數第k個結點，

struct ListNode* FindKthToTail(struct ListNode* pListHead, int k ) 
{
    struct ListNode* fast = pListHead;
    struct ListNode* slow = pListHead;
    //這里需要注意，如果k給的值大于鏈表的長度，則也要結束回圈，最后判斷回傳NULL
    while(k  && fast)
    {
        fast = fast->next;
        k--;
    }
    if(fast == NULL && k)
        return NULL;
    while(fast)
    {
        fast = fast->next;
        slow = slow->next;
    }
    return slow;
}

3.求2個相交鏈表的交點

定義2個指標用來去求2條鏈表的長度，然后根據鏈表的長度定義一個指向長鏈表的指標LongList和指向短鏈表的指標ShortList，讓LongList先走2條鏈表的長度差的絕對值的步數，然后LongList和ShortList一起走，并且同時進行判斷，如果LongList == ShortList那么第一個相等的點就是2條鏈表的交點，

struct ListNode* getIntersectionNode(struct ListNode *headA, struct ListNode *headB) 
{
    //思路：先讓長的鏈表的指標走它比短的長多少的步數，然后兩個指標同時移動進行比較
    struct ListNode* curA = headA;
    struct ListNode* curB = headB;
    int LA = 0;
    int LB = 0;
    while(curA)
    {
        LA++;
        curA = curA->next;
    }     
    while(curB)
    {
        LB++;
        curB = curB->next;
    }
    //定義一個長鏈表的指標和一點短鏈表的指標
    struct ListNode* LongList = LA>LB?headA:headB;  
    struct ListNode* ShortList = LA<=LB?headA:headB;  
    //求出間隔的步數
    int gap = abs(LA-LB);//abs求的是絕對值
    while(gap--)
    {
        LongList = LongList->next;
    }
    //找第一個相同結點，然后return該點
    while(LongList)
    {
        if(LongList == ShortList)
            return LongList;
        LongList = LongList->next;
        ShortList = ShortList->next;
    }
    //兩條鏈表不相交,回傳NULL
    return NULL;
}

4.判斷鏈表是否成環

定義快指標fast和慢指標slow，快指標每次走2步，慢指標每次走1步，如果快指標再次與慢指標相遇(fast == slow)，則該鏈表成環，否則不成環，【這里快指標的步數可以改變，但要注意有可能會出現快指標永遠追不上慢指標的情況，】

快指標每次和慢指標間距縮小1，所以如果該鏈表成環的話，快指標會與慢指標再次重合，

bool hasCycle(struct ListNode *head) 
{
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    //通過定義一個快指標和慢指標，如果快指標能追上慢指標，則該鏈表有環，否則該鏈表無環
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        //快指標追上了慢指標
        if(fast == slow)
            return true;
    }
    //如果快指標遇到NULL，則該鏈表肯定不成環
    return false;
}

5.求成環鏈表進環的第一個結點(入環點)

在上一個題的基礎上，我們可以求出fast和slow相遇點，然后定義一個指標meet指向該結點，再定義一個指向頭結點的指標head，head和meet一起走，它們的值相同的那個點就是入環點，

struct ListNode* detectCycle(struct ListNode *head) 
{
    //通過head和fast與slow的交點(meet)這兩個指標進行查找入環點
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(fast == slow)
            break;
    }
    if(fast == NULL || fast->next == NULL)
        return NULL;
    struct ListNode* meet = fast;
    while(head != meet)
    {
        head = head->next;
        meet = meet->next;
    }
    return head;
}