無法高效獲取長度，無法根據偏移快速訪問元素，是鏈表的兩個劣勢。然而面試的時候經常碰見諸如獲取倒數第k個元素，獲取中間位置的元素，判斷鏈表是否存在環，判斷環的長度等和長度與位置有關的問題。這些問題都可以通過靈活運用雙指針來解決。

Tips：雙指針并不是固定的公式，而是一種思維方式~

先來看"倒數第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 恰好指向中間兩個結點的靠前一個(可以考慮下如何使其指向后一個結點呢？

下述代碼實現了 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;} };

是否存在環的問題。如果將尾結點的 next 指針指向其他任意一個結點，那么鏈表就存在了一個環。

上一部分中，總結快慢指針的特性 —— 每輪移動之后兩者的距離會加一。下面會繼續用該特性解決環的問題。
當一個鏈表有環時，快慢指針都會陷入環中進行無限次移動，然后變成了追及問題。想象一下在操場跑步的場景，只要一直跑下去，快的總會追上慢的。當兩個指針都進入環后，每輪移動使得慢指針到快指針的距離增加一，同時快指針到慢指針的距離也減少一，只要一直移動下去，快指針總會追上慢指針。

根據上述表述得出，如果一個鏈表存在環，那么快慢指針必然會相遇。實現代碼如下：

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;} };

最后一個問題，如果存在環，如何判斷環的長度呢？方法是，快慢指針相遇后繼續移動，直到第二次相遇。兩次相遇間的移動次數即為環的長度。

作者：Time-Limit
鏈接：https://leetcode-cn.com/problems/linked-list-cycle/solution/yi-wen-gao-ding-chang-jian-de-lian-biao-wen-ti-h-2/
來源：力扣（LeetCode）

猜你喜歡：👇🏻
?【Leetcode】Python 代碼本地構造二叉樹、鏈表
?【Leetcode】創建鏈表
?【Leetcode】二叉樹展開為列表（遞歸思想）

總結

以上是生活随笔為你收集整理的【Leetcode】大神总结的链表常见面试问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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