一、簡介：什么是快慢指針？

快慢指針，顧名思義，無非就是設置一個快指針，一個慢指針，初始化的時候，快指針和慢指針都指向鏈表的頭結點，前進的時候一個在前一個在后，結合起來可以十分巧妙的解決鏈表中的一些問題；

看完本文可以解決leetcode141題(簡單)以及leetcode142題(中等)。
雙指針算法之快慢指針(二)：力扣【尋找鏈表的第N個點】leetcode-876、19

二、典例一：判斷鏈表是否有環

這個應該屬于鏈表算法的經典的操作了，如果一個單鏈表有環，一個指針是判斷不出來的，因為鏈表尾部和頭部"鏈接"在一起，形成了一個死循環。

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

如果使用一個指針：上述的代碼，如果沒有環的話，head 指針最后就會走到NULL,就會返回 false。到那時如果鏈表是有環的，就麻煩了，head會在循環中一直出不來的，自然不會有結果~
但是，如果設置快慢兩個指針，快指針走到null的時候，就可以得知這個鏈表是沒有環的；如果快慢指針相遇了，說明快指針肯定已經走了幾圈了，這個鏈表肯定是有環的。
比較經典的就是leetcode的141題

1、題目描述：

2、思路以及代碼

只要快慢指針相遇，說明是有環的,所以我們這里設置快指針 fast 一次走兩步，慢指針 slow一次就一步；

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:bool hasCycle(ListNode *head) {ListNode *fast,*slow;fast = slow = head; // 初始都頭節點的位置while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;if (fast == slow) { // 相遇了return true;}}return false;} };

三、典例二：判斷鏈表中是否有環，有環就返回環的起始位置

剛剛的快慢指針判斷鏈表是不是有環其實還是很好理解的，但是進一步提升的話，判斷出來有環之后，返回這個環的開始位置, 不僅僅需要判斷是不是有環，有環的話還有知道環是where 開始的。

比較經典的就是leetcode的142題

1、題目描述

2、題目分析

在這里，我們先回到上一題的解法，使用快慢指針去判斷是不是有環，如果快慢指針相遇了，就是有環，那么，快慢指針相遇在哪一個點呢？這個點有什么特別之處嗎？除了相遇的點，我們還應該注意到鏈表頭結點，相遇點，環開始結點。
其實142題的核心，確實就在于分析一下這3個點，下面我們就來分析一下：

下圖的聲明：
O 是鏈表頭結點
A 是環開始的點
B 是快指針和滿指針相遇的點
K 是慢指針 slow 在快慢指針相遇之時走的路程，即推：快指針是 2 K
L(OA)是 從O 開始 第一次遇到 A 走的路長，就是下圖藍色部分
L(AB)是 從A 開始 第一次遇到 B 走的路長，就是下圖紅色部分
L環 是 從A 開始 再一次遇到 A 走的路長 其實就是k了
L(BA)是 從B開始 第一次遇到 A 走的路長。就是下圖綠色部分

根據下圖的計算，我們可以知道 L(OA）和 L(BA) 的長度是一樣的。

由于 L(OA）和 L(BA) 的長度是一樣的，所以我們在快指針 fast 和滿指針 slow 相遇的時候，在B點相遇的時候，

1、快指針 fast 繼續前進，速度和慢指針一樣
2、慢指針 slow 返回鏈表頭結點 O點，
3、快慢指針的速度保持一致，各自繼續前進

那么，快慢指針下一次相遇的點是哪里？沒錯，就是 A 點，就是環開始的結點。

3、解題代碼

由此，我們可以寫出下面的偽代碼：

ListNode detectCycle(ListNode head) {快慢指針初始化，都在頭結點while (fast != null && fast.next != null) {快指針一次兩步慢指針一次一步if (快指針 = 慢指針) {//即相遇 此時在 B 點慢指針回到頭結點；while (slow != fast) {快慢指針繼續走，一次一步；}return slow;}}return NULL; }

隨后就可以寫出全部的代碼了：

class Solution { public:ListNode *detectCycle(ListNode *head) {ListNode *fast,*slow;fast = slow = head;while (fast != NULL && fast->next != NULL) {fast = fast->next->next;slow = slow->next;if (fast == slow) {slow = head;while (fast != slow) {fast = fast->next; slow = slow->next;}return slow;}}return NULL;} };

總結

以上是生活随笔為你收集整理的双指针算法之快慢指针(一)：力扣【判断链表是否有环】leetcode-141、142的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。