快慢指針、左右指針的常見算法

作者：labuladong

公眾號：labuladong

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

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

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

一、快慢指針的常見算法

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

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

這屬于鏈表最基本的操作了，學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)應(yīng)該對這個算法思想都不陌生。

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

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

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

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

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

力扣第 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、已知鏈表中含有環(huán)，返回這個環(huán)的起始位置

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

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函數(shù) slow=head; while(slow!=fast){ fast=fast.next; slow=slow.next; } returnslow; }

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

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

fast一定比slow多走了k步，這多走的k步其實就是fast指針在環(huán)里轉(zhuǎn)圈圈，所以k的值就是環(huán)長度的「整數(shù)倍」。

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

那么fast肯定早早就進(jìn)環(huán)里轉(zhuǎn)圈圈了，而且肯定會轉(zhuǎn)好多圈，這不就是環(huán)長度的整數(shù)倍嘛。

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

巧的是，如果從相遇點(diǎn)繼續(xù)前進(jìn)k - m步，也恰好到達(dá)環(huán)起點(diǎn)。你甭管fast在環(huán)里到底轉(zhuǎn)了幾圈，反正走k步可以到相遇點(diǎn)，那走k - m步一定就是走到環(huán)起點(diǎn)了：

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

3、尋找鏈表的中點(diǎn)

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

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

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

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

尋找鏈表中點(diǎn)的一個重要作用是對鏈表進(jìn)行歸并排序。

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

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

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

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

我們的思路還是使用快慢指針，讓快指針先走n步，然后快慢指針開始同速前進(jìn)。這樣當(dāng)快指針走到鏈表末尾null時，慢指針?biāo)诘奈恢镁褪堑箶?shù)第n個鏈表節(jié)點(diǎn)（n不會超過鏈表長度）。

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

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

二、左右指針的常用算法

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

1、二分查找

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

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、兩數(shù)之和

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

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

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

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

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

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

4、滑動窗口算法

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

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

責(zé)任編輯：PSY

原文標(biāo)題：雙指針技巧直接秒殺五道算法題

文章出處：【微信公眾號：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請注明出處。