許久不見，那么這是最后倒數第三題了，這道題我們來看一下環形鏈表。
老規矩貼鏈接：141. 環形鏈表 - 力扣（LeetCode）
目錄
倒數第k個元素
獲取中間元素的問題。
雙指針
來，大致看一下題目，這道題目需要我們做什么？?需要我們去判斷，這個鏈表內存不存在環，那我們比較的是什么？比較值肯定是不行，那我們發現，能不能在遍歷到一定程度以后，讓這個節點的指針域等于我們之前遍歷過的節點的指針域。那我們發現我們遍歷是存儲不了數據的。那么思路就卡死了。
無法高效獲取長度，無法根據偏移快速訪問元素，是鏈表的兩個劣勢。然而面試的時候經常碰見諸如獲取倒數第k個元素，獲取中間位置的元素，判斷鏈表是否存在環，判斷環的長度等和長度與位置有關的問題。這些問題都可以通過靈活運用雙指針來解決。
當然雙指針是一種思維，而不是一個公式。這一點需要讀者謹記。
直接從雙指針開始講起會顯得很云里霧里，所以我們這里鋪墊兩道題目來穿插這里的思想。對于鏈表的長度和偏移量的操作需要慎之又慎。
倒數第k個元素
先來看"倒數第k個元素的問題"。設有兩個指針 p 和 q，初始時均指向頭結點。首先，先讓 p 沿著 next 移動 k 次。此時，p 指向第 k+1個結點，q 指向頭節點，兩個指針的距離為 k 。然后，同時移動 p 和 q，直到 p 指向空，此時 q 即指向倒數第 k 個結點。可以參考下圖來理解：
這里就是固定兩人的思想，講的比較感性一點就像兩人推進，前一個人推進結果踩空了之后，那么后一個人就已經知道自己所在位置是對的了。代碼放在下面供大家參考。
class Solution {
public:ListNode* getKthFromEnd(ListNode* head, int k) {ListNode *p = head, *q = head; //初始化while(k--) { //將 p指針移動 k 次p = p->next;}while(p != nullptr) {//同時移動，直到 p == nullptrp = p->next;q = q->next;}return q;}
};獲取中間元素的問題。
設有兩個指針 fast 和 slow，初始時指向頭節點。每次移動時，fast向后走兩次，slow向后走一次，直到 fast 無法向后走兩次。這使得在每輪移動之后。fast 和 slow 的距離就會增加一。設鏈表有 n 個元素，那么最多移動 n/2 輪。當 n 為奇數時，slow 恰好指向中間結點，當 n 為 偶數時，slow 恰好指向中間兩個結點的靠前一個(可以考慮下如何使其指向后一個結點呢？）
跟上面不一樣的是，這里改變的是兩個指針的跨度。那么到底怎么讓偶數的時候讓他指向往后一個節點呢？一種簡單的方法是在?fast?無法移動兩步時，讓?slow?再移動一步。這樣，slow?將從中間兩個節點的前一個節點移動到后一個節點。?下述代碼實現了 n 為偶數時慢指針指向靠后結點。
class Solution {
public:ListNode* middleNode(ListNode* head) {ListNode *p = head, *q = head;while(q != nullptr && q->next != nullptr) {p = p->next;q = q->next->next;}return p;}
};雙指針
那我們再回來看我們卡在了哪里。
我們在開頭的時候為什么卡住了？因為我們想的是單指針的循環遍歷問題，考慮遍歷后的節點指針域如何儲存，或者是再次讀取。
那么根據上一個引題我們來總結快慢指針的特性 —— 每輪移動之后兩者的距離會加一。??
下面會繼續用該特性解決環的問題。
當一個鏈表有環時，快慢指針都會陷入環中進行無限次移動，然后變成了追及問題。想象一下在操場跑步的場景，只要一直跑下去，快的總會追上慢的。當兩個指針都進入環后，每輪移動使得慢指針到快指針的距離增加一，同時快指針到慢指針的距離也減少一，只要一直移動下去，快指針總會追上慢指針。也就是說，套圈了唄！
哈哈，我找了一張很清楚的動圖來給大家演示，根據上述表述得出，如果一個鏈表存在環，那么快慢指針必然會相遇！！！
所以這里再重新提出來兩個問題：
1.為什么快指針每次走兩步，慢指針走一步可以？
假設鏈表帶環，兩個指針最后都會進入環，快指針先進環，慢指針后進環。當慢指針剛進環時，可
能就和快指針相遇了，最差情況下兩個指針之間的距離剛好就是環的長度。此時，兩個指針每移動
一次，之間的距離就縮小一步，不會出現每次剛好是套圈的情況，因此：在滿指針走到一圈之前，
快指針肯定是可以追上慢指針的，即相遇。
2.快指針一次走3步，走4步，...n步行嗎？
最后貼一下代碼
class Solution {
public:bool hasCycle(ListNode *head) {ListNode *slow = head;ListNode *fast = head;while(fast != nullptr) {fast = fast->next;if(fast != nullptr) {fast = fast->next;}if(fast == slow) {return true;}slow = slow->next;}return nullptr;}
};好了，這道題就講到這里
如果你覺得對你有幫助，可以點贊關注加收藏，感謝您的閱讀，我們下一篇文章再見。
一步步來，總會學會的，首先要懂思路，才能有東西寫。
