作者：labuladong

公眾號：labuladong

本文是一兩年前發過的一篇文章，當時沒多少人看，現在由于賬號遷移的原因公眾號里都搜索不到了，我就重新加工了一下，并且添加了新內容，直接套雙指針技巧秒殺 5 道算法題。

其實，鼎鼎有名的「滑動窗口算法」就是一種雙指針技巧，我們之前的爆文我寫了套框架，把滑動窗口算法變成了默寫題就有這么一段：

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

一、快慢指針的常見算法

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

1、判定鏈表中是否含有環

這屬于鏈表最基本的操作了，學習數據結構應該對這個算法思想都不陌生。

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

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

booleanhasCycle(ListNodehead){ while(head!=null) head=head.next; returnfalse; }

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

經典解法就是用兩個指針，一個跑得快，一個跑得慢。如果不含有環，跑得快的那個指針最終會遇到null，說明鏈表不含環；如果含有環，快指針最終會超慢指針一圈，和慢指針相遇，說明鏈表含有環。

力扣第 141 題就是這個問題，解法代碼如下：

booleanhasCycle(ListNodehead){ ListNodefast,slow; fast=slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow)returntrue; } returnfalse; }

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

這個問題一點都不困難，有點類似腦筋急轉彎，先直接看代碼：

ListNodedetectCycle(ListNodehead){ ListNodefast,slow; fast=slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; if(fast==slow)break; } //上面的代碼類似hasCycle函數 slow=head; while(slow!=fast){ fast=fast.next; slow=slow.next; } returnslow; }

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

第一次相遇時，假設慢指針slow走了k步，那么快指針fast一定走了2k步：

fast一定比slow多走了k步，這多走的k步其實就是fast指針在環里轉圈圈，所以k的值就是環長度的「整數倍」。

說句題外話，之前還有讀者爭論為什么是環長度整數倍，我舉個簡單的例子你就明白了，我們想一想極端情況，假設環長度就是 1，如下圖：

那么fast肯定早早就進環里轉圈圈了，而且肯定會轉好多圈，這不就是環長度的整數倍嘛。

言歸正傳，設相遇點距環的起點的距離為m，那么環的起點距頭結點head的距離為k - m，也就是說如果從head前進k - m步就能到達環起點。

巧的是，如果從相遇點繼續前進k - m步，也恰好到達環起點。你甭管fast在環里到底轉了幾圈，反正走k步可以到相遇點，那走k - m步一定就是走到環起點了：

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

3、尋找鏈表的中點

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

力扣第 876 題就是找鏈表中點的題目，解法代碼如下：

ListNodemiddleNode(ListNodehead){ ListNodefast,slow; fast=slow=head; while(fast!=null&&fast.next!=null){ fast=fast.next.next; slow=slow.next; } //slow就在中間位置 returnslow; }

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

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

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

但是現在你學會了找到鏈表的中點，就能實現鏈表的二分了。關于歸并排序的具體內容本文就不具體展開了。

4、尋找鏈表的倒數第n個元素

這是力扣第 19 題「刪除鏈表的倒數第n個元素」，先看下題目：

我們的思路還是使用快慢指針，讓快指針先走n步，然后快慢指針開始同速前進。這樣當快指針走到鏈表末尾null時，慢指針所在的位置就是倒數第n個鏈表節點（n不會超過鏈表長度）。

解法比較簡單，直接看代碼吧：

ListNoderemoveNthFromEnd(ListNodehead,intn){ ListNodefast,slow; fast=slow=head; //快指針先前進n步 while(n-->0){ fast=fast.next; } if(fast==null){ //如果此時快指針走到頭了， //說明倒數第n個節點就是第一個節點 returnhead.next; } //讓慢指針和快指針同步向前 while(fast!=null&&fast.next!=null){ fast=fast.next; slow=slow.next; } //slow.next就是倒數第n個節點，刪除它 slow.next=slow.next.next; returnhead; }

二、左右指針的常用算法

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

1、二分查找

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

intbinarySearch(int[]nums,inttarget){ intleft=0; intright=nums.length-1; while(left<=?right)?{ ????????int?mid?=?(right?+?left)?/?2; ????????if(nums[mid]?==?target) ????????????return?mid;? ????????else?if?(nums[mid]?target) right=mid-1; } return-1; }

2、兩數之和

直接看力扣第 167 題「兩數之和 II」吧：

只要數組有序，就應該想到雙指針技巧。這道題的解法有點類似二分查找，通過調節left和right可以調整sum的大小：

int[]twoSum(int[]nums,inttarget){ intleft=0,right=nums.length-1; while(lefttarget){ right--;//讓sum小一點 } } returnnewint[]{-1,-1}; }

3、反轉數組

一般編程語言都會提供reverse函數，其實非常簡單，力扣第 344 題是類似的需求，讓你反轉一個char[]類型的字符數組，我們直接看代碼吧：

voidreverseString(char[]arr){ intleft=0; intright=arr.length-1; while(left

4、滑動窗口算法

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

不過這類算法是有框架模板的，而且前文我寫了首詩，把滑動窗口算法變成了默寫題就講解了「滑動窗口」算法模板，幫大家秒殺幾道子串匹配的問題，如果沒有看過，建議去看看。

責任編輯：PSY

原文標題：雙指針技巧直接秒殺五道算法題

文章出處：【微信公眾號：算法與數據結構】歡迎添加關注！文章轉載請注明出處。