【數據結構】快慢指針

一、快慢指針的原理

定義：
????????快指針：每次移動兩步
? ? ? ? 慢指針：每次移動一步
終止條件：
? ? ? ? 當快指針到達鏈表末尾時停止
事件復雜度：
? ? ? ? 始終為O(n),僅需依次遍歷
空間復雜度：
? ? ? ? 僅需兩個指針變量

二、快慢指針的典型應用場景

1、首先制作一個鏈表的節點
?

#include <iostream>
#include <vector>struct ListNode {int val;ListNode* next;ListNode(int x) :val(x), next(nullptr){}ListNode(int x, ListNode *_next):val(x),next(_next){}
};//傳入列表生成list鏈
ListNode* makeNodeList(std::vector<int> vec)
{ListNode* outNode = nullptr;for (int i = vec.size() - 1; i >= 0 ; i--){outNode = new ListNode(vec[i],outNode);}return outNode;}//遍歷輸出鏈表
void traverseNodeList(ListNode* node)
{while (node){std::cout << node->val << " ";node = node->next;}std::cout << std::endl;
}//回收資源
void reclaim(ListNode* node)
{if (node->next){reclaim(node->next);}delete node;
}int main()
{std::vector<int> vec{ 1,2,3,4,5 };ListNode *node = makeNodeList(vec);traverseNodeList(node);reclaim(node);return 0;
}

2、檢測鏈表是否有環

代碼如下：

bool haveLoop(ListNode* node)
{ListNode* fast = node;ListNode* slow = node;while (fast != nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;if (fast == slow){return true;		//快指針追上了滿指針，有環}}return false;
}int main()
{ListNode* node5 = new ListNode(5);ListNode* node4 = new ListNode(4, node5);ListNode* node3 = new ListNode(3, node4);ListNode* node2 = new ListNode(2, node3);ListNode* node1 = new ListNode(1, node2);node5->next = node2;if (haveLoop(node1)){std::cout << "有環" << std::endl;}else {std::cout << "沒環" << std::endl;}return 0;
}

3、找到鏈表的中間節點

ListNode* middileNode(ListNode* node)
{ListNode *fast = node, *slow = node;while (fast && fast->next) {		//如果fast的next為nullptr,則下面的next->next就找不第二個next了fast = fast->next->next;slow = slow->next;}return slow;
}int main()
{std::vector<int> vec{ 1,2,3,4,5 };ListNode *node = makeNodeList(vec);ListNode *midNode = middileNode(node);std::cout << "奇數個中間節點是" << midNode->val << std::endl;std::vector<int> vec2{ 1,2,3,4,5,6 };ListNode* node2 = makeNodeList(vec2);ListNode* midNode2 = middileNode(node2);std::cout << "偶數個中間節點是" << midNode->val << std::endl;return 0;
}

4、尋找鏈表的環入口

代碼如下：
（因為用到了前面判斷是否時環的函數，所以代碼都放這里了）

#include <iostream>
#include <vector>struct ListNode {int val;ListNode* next;ListNode(int x) :val(x), next(nullptr){}ListNode(int x, ListNode *_next):val(x),next(_next){}
};//傳入列表生成list鏈
ListNode* makeNodeList(std::vector<int> vec)
{ListNode* outNode = nullptr;for (int i = vec.size() - 1; i >= 0 ; i--){outNode = new ListNode(vec[i],outNode);}return outNode;}//遍歷輸出鏈表
void traverseNodeList(ListNode* node)
{while (node){std::cout << node->val << " ";node = node->next;}std::cout << std::endl;
}//回收資源
void reclaim(ListNode* node)
{if (node->next){reclaim(node->next);}delete node;
}bool haveLoop(ListNode* node)
{ListNode* fast = node;ListNode* slow = node;while (fast != nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;if (fast == slow){return true;		//快指針追上了滿指針，有環}}return false;
}ListNode* middileNode(ListNode* node)
{ListNode *fast = node, *slow = node;while (fast && fast->next) {		//如果fast的next為nullptr,則下面的next->next就找不第二個next了fast = fast->next->next;slow = slow->next;}return slow;
}ListNode* entranceNode(ListNode* node)
{if (!haveLoop(node)){return nullptr;				//如果不含有環路，返回空指針}ListNode* fast = node, * slow = node;while (fast && fast->next){fast = fast->next->next;slow = slow->next;if (fast == slow){break;}}slow = node;while (fast != slow){fast = fast->next;slow = slow->next;}return slow;
}int main()
{ListNode* node5 = new ListNode(5);ListNode* node4 = new ListNode(4, node5);ListNode* node3 = new ListNode(3, node4);ListNode* node2 = new ListNode(2, node3);ListNode* node1 = new ListNode(1, node2);node5->next = node3;ListNode* node = entranceNode(node1);	//Node節點std::cout << "入口節點值為" << node->val << std::endl;return 0;
}

5、判斷回文鏈表
?
代碼如下：

#include <iostream>
#include <vector>struct ListNode {int val;ListNode* next;ListNode(int x) :val(x), next(nullptr){}ListNode(int x, ListNode *_next):val(x),next(_next){}
};//傳入列表生成list鏈
ListNode* makeNodeList(std::vector<int> vec)
{ListNode* outNode = nullptr;for (int i = vec.size() - 1; i >= 0 ; i--){outNode = new ListNode(vec[i],outNode);}return outNode;}//遍歷輸出鏈表
void traverseNodeList(ListNode* node)
{while (node){std::cout << node->val << " ";node = node->next;}std::cout << std::endl;
}//回收資源
void reclaim(ListNode* node)
{if (node->next){reclaim(node->next);}delete node;
}bool haveLoop(ListNode* node)
{ListNode* fast = node;ListNode* slow = node;while (fast != nullptr && fast->next != nullptr){fast = fast->next->next;slow = slow->next;if (fast == slow){return true;		//快指針追上了滿指針，有環}}return false;
}ListNode* middileNode(ListNode* node)
{ListNode *fast = node, *slow = node;while (fast && fast->next) {		//如果fast的next為nullptr,則下面的next->next就找不第二個next了fast = fast->next->next;slow = slow->next;}return slow;
}ListNode* entranceNode(ListNode* node)
{if (!haveLoop(node)){return nullptr;				//如果不含有環路，返回空指針}ListNode* fast = node, * slow = node;while (fast && fast->next){fast = fast->next->next;slow = slow->next;if (fast == slow){break;}}slow = node;while (fast != slow){fast = fast->next;slow = slow->next;}return slow;
}bool isSymmeNode(ListNode* node)
{//用前面的函數找到中間節點ListNode* midNode = middileNode(node);//反轉中間節點后面的節點// 321 -> 123// 3 2 1// 3		21// 2 3		1// 1 2 3ListNode* temp;ListNode* Lnode = midNode;ListNode* Rnode = nullptr;while (Lnode){temp = Lnode->next;Lnode->next = Rnode;		//讓先放進來的值朝著后面排Rnode = Lnode;Lnode = temp;}//第三步、比較前后的值是否相同while(Rnode){if (node->val != Rnode->val){return false;}else {node = node->next;Rnode = Rnode->next;}}return true;
}int main()
{std::vector<int> vec = { 1,2,3,3,2,1 };ListNode* Node = makeNodeList(vec);if (isSymmeNode(Node)){std::cout << "是回文鏈" << std::endl;}else {std::cout << "不是回文鏈" << std::endl;}return 0;
}

6、找到鏈表的倒數第K個節點

ListNode* getKthFromEnd(ListNode* node, int k)
{ListNode* fast = node, * slow = node;for (int i = 0; i < k; i++){if (fast && fast->next){fast = fast->next;}else {return nullptr;}}while (fast){fast = fast->next;slow = slow->next;}return slow;
}int main()
{std::vector<int> vec = { 1,2,3,4,5,6 };ListNode* Node = makeNodeList(vec);std::cout << "倒數第3節點的值是" << getKthFromEnd(Node, 3)->val << std::endl;return 0;
}

三、快慢指針在實際開發中的應用
????????下面是DeepseeK給出的，個人認為是從判斷環，找中點，業務需求速率不同這三個角度演化。還沒實踐過。后面有實踐應該會貼鏈接在這里。

????????PS:夜已深，學生時期聽的歌真有品味啊，當世界年輕時

1.?資源管理與循環檢測

場景：在內存管理、文件系統或網絡協議中，需要檢測資源引用是否形成循環依賴。
- 示例：
  - 垃圾回收（GC）：某些垃圾回收算法需要檢測對象之間的循環引用（如標記-清除算法）。通過快慢指針可以高效判斷對象引用鏈中是否存在環，避免內存泄漏。
  - 文件系統的符號鏈接：檢測符號鏈接是否形成環（如?ln -s file1 file2; ln -s file2 file1），避免程序陷入死循環遍歷。

2.?數據結構的維護與優化

場景：在自定義鏈表結構或緩存系統中，需要高效操作鏈表。
- 示例：
  - 緩存淘汰策略：在實現類似 LRU（最近最少使用）緩存時，若需手動管理鏈表（而非使用現成庫），快慢指針可用于快速定位中間節點或批量調整緩存順序。
  - 鏈表合并與分割：在分布式系統中合并多個有序鏈表（如日志合并），通過快慢指針找到中點后分治處理（類似歸并排序）。

3.?網絡與協議處理

場景：處理網絡數據包的順序或超時檢測。
- 示例：
  - 心跳檢測：在長連接中，若用鏈表維護心跳包的時間戳，快指針（高頻檢測）和慢指針（低頻統計）可協同判斷連接健康狀態。
  - 數據包亂序重組：通過快慢指針分離已確認和待確認的數據包鏈表。

4.?并發與多線程編程

場景：在無鎖數據結構或任務調度中，檢測潛在的死鎖或競態條件。
- 示例：
  - 任務隊列管理：在生產者-消費者模型中，快指針快速推進任務處理，慢指針統計未處理任務量，動態調整隊列負載。
  - 死鎖檢測：若線程等待關系形成鏈表式依賴，快慢指針可輔助檢測循環等待（需結合線程調度器的元數據）。

5.?系統性能分析與調試

場景：在性能分析工具或調試器中，追蹤程序執行路徑。
- 示例：
  - 調用鏈分析：在分布式追蹤系統（如 OpenTelemetry）中，若調用鏈因異常形成環（如 A→B→A），快慢指針可快速定位問題節點。
  - 棧溢出檢測：通過快慢指針監控遞歸調用的深度（慢指針記錄常規檢查點，快指針快速探測棧增長）。