我認為雙指針技巧還可以分為兩類，一類是「快慢指針」，一類是「左右指針」。前者解決主要解決鏈表中的問題，比如典型的判定鏈表中是否包含環(huán)；后者主要解決數(shù)組（或者字符串）中的問題，比如二分查找。

一、快慢指針的常見算法

快慢指針一般都初始化指向鏈表的頭結(jié)點 head，前進時快指針 fast 在前，慢指針 slow 在后，巧妙解決一些鏈表中的問題。

1 、判定鏈表中是否含有環(huán)

這應(yīng)該屬于鏈表最基本的操作了，如果讀者已經(jīng)知道這個技巧，可以跳過。

單鏈表的特點是每個節(jié)點只知道下一個節(jié)點，所以一個指針的話無法判斷鏈表中是否含有環(huán)的。

如果鏈表中不含環(huán)，那么這個指針最終會遇到空指針 null 表示鏈表到頭了，這還好說，可以判斷該鏈表不含環(huán)。

boolean hasCycle(ListNode head) {
    while (head != null)
        head = head.next;
    return false;
}

但是如果鏈表中含有環(huán)，那么這個指針就會陷入死循環(huán)，因為環(huán)形數(shù)組中沒有 null 指針作為尾部節(jié)點。

經(jīng)典解法就是用兩個指針，一個每次前進兩步，一個每次前進一步。如果不含有環(huán)，跑得快的那個指針最終會遇到 null，說明鏈表不含環(huán)；如果含有環(huán)，快指針最終會超慢指針一圈，和慢指針相遇，說明鏈表含有環(huán)。

2 、已知鏈表中含有環(huán)，返回這個環(huán)的起始位置

這個問題其實不困難，有點類似腦筋急轉(zhuǎn)彎，先直接看代碼：

可以看到，當快慢指針相遇時，讓其中任一個指針重新指向頭節(jié)點，然后讓它倆以相同速度前進，再次相遇時所在的節(jié)點位置就是環(huán)開始的位置。這是為什么呢？

第一次相遇時，假設(shè)慢指針 slow 走了 k 步，那么快指針 fast 一定走了 2k 步，也就是說比 slow 多走了 k 步（也就是環(huán)的長度）。

設(shè)相遇點距環(huán)的起點的距離為 m，那么環(huán)的起點距頭結(jié)點 head 的距離為 k - m，也就是說如果從 head 前進 k - m 步就能到達環(huán)起點。

巧的是，如果從相遇點繼續(xù)前進 k - m 步，也恰好到達環(huán)起點。

所以，只要我們把快慢指針中的任一個重新指向 head，然后兩個指針同速前進，k - m 步后就會相遇，相遇之處就是環(huán)的起點了。

3 、尋找鏈表的中點

類似上面的思路，我們還可以讓快指針一次前進兩步，慢指針一次前進一步，當快指針到達鏈表盡頭時，慢指針就處于鏈表的中間位置。

ListNode slow, fast;
slow = fast = head;
while (fast != null && fast.next != null) {
    fast = fast.next.next;
    slow = slow.next;
}
// slow 就在中間位置
return slow;

當鏈表的長度是奇數(shù)時，slow 恰巧停在中點位置；如果長度是偶數(shù)，slow 最終的位置是中間偏右：

尋找鏈表中點的一個重要作用是對鏈表進行歸并排序。

回想數(shù)組的歸并排序：求中點索引遞歸地把數(shù)組二分，最后合并兩個有序數(shù)組。對于鏈表，合并兩個有序鏈表是很簡單的，難點就在于二分。

但是現(xiàn)在你學(xué)會了找到鏈表的中點，就能實現(xiàn)鏈表的二分了。關(guān)于歸并排序的具體內(nèi)容本文就不具體展開了。

4 、尋找鏈表的倒數(shù)第 k 個元素

我們的思路還是使用快慢指針，讓快指針先走 k 步，然后快慢指針開始同速前進。這樣當快指針走到鏈表末尾 null 時，慢指針所在的位置就是倒數(shù)第 k 個鏈表節(jié)點（為了簡化，假設(shè) k 不會超過鏈表長度）：

ListNode slow, fast;
slow = fast = head;
while (k-- > 0) 
    fast = fast.next;

while (fast != null) {
    slow = slow.next;
    fast = fast.next;
}
return slow;

二、左右指針的常用算法

左右指針在數(shù)組中實際是指兩個索引值，一般初始化為 left = 0, right = nums.length - 1 。

1 、二分查找

前文 [二分查找算法詳解] 有詳細講解，這里只寫最簡單的二分算法，旨在突出它的雙指針特性：

2 、兩數(shù)之和

直接看一道 LeetCode 題目吧：

只要數(shù)組有序，就應(yīng)該想到雙指針技巧。這道題的解法有點類似二分查找，通過調(diào)節(jié) left 和 right 可以調(diào)整 sum 的大小：

3 、反轉(zhuǎn)數(shù)組

void reverse(int[] nums) {
    int left = 0;
    int right = nums.length - 1;
    while (left < right) {
        // swap(nums[left], nums[right])
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        left++; right--;
    }
}

4 、滑動窗口算法

這也許是雙指針技巧的最高境界了，如果掌握了此算法，可以解決一大類子字符串匹配的問題，不過「滑動窗口」算法比上述的這些算法稍微復(fù)雜些。

幸運的是，這類算法是有框架模板的，下篇文章就準備講解「滑動窗口」算法模板，幫大家秒殺幾道 LeetCode 子串匹配的問題。