[TOC] ## 141 環形鏈表 給定一個鏈表，判斷鏈表中是否有環。 為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。 一、利用map 二、利用雙指針（快慢指針） ``` class?Solution?{ public: bool?hasCycle(ListNode?*head)?{ //-------快慢指針（12ms） //-------快指針一次走兩步，慢指針一次走一步，如果鏈表有環，那么兩個指針始終會相遇。 //-------時間復雜度?O(n)，空間復雜度?O(1) if?(head?==?NULL)?returnfalse; ????????ListNode*?fastHead?=?head->next; while(fastHead?!=?NULL?&&?head?!=?NULL?&&?fastHead->next?!=?NULL) ????????{ if?(fastHead?==?head)?return true; ????????????head?=?head->next; ????????????fastHead?=?fastHead->next->next; ????????} return false;???????? ????} }; ``` ## 142 環形鏈表二 [https://leetcode-cn.com/problems/linked-list-cycle-ii/](https://leetcode-cn.com/problems/linked-list-cycle-ii/) 給定一個鏈表，返回鏈表開始入環的第一個節點。?如果鏈表無環，則返回?null。 為了表示給定鏈表中的環，我們使用整數 pos 來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。 如果 pos 是 -1，則在該鏈表中沒有環。 說明：不允許修改給定的鏈表。  ``` /\*\* ?\*?Definition?for?singly-linked?list. ?\*?struct?ListNode?{ ?\*?????int?val; ?\*?????ListNode?\*next; ?\*?????ListNode(int?x)?:?val(x),?next(NULL)?{} ?\*?}; ?\*/ class?Solution?{ public: ????ListNode?*detectCycle(ListNode?\*head)?{ /\*快慢指針。快指針一次走兩步，慢指針一次走一步,當快指針和慢指針相遇時，head->環起點的地方=?相遇點fast指針?相同方向走到->環起點的地方\*/ if?(head?==?NULL?||?head->next?==?NULL) ????????{ return?NULL; ????????} ????????ListNode*?fastNode?=?head; ????????ListNode*?slowNode?=?head; while(fastNode?!=?NULL?&&?fastNode->next?!=NULL) ????????{ ????????????fastNode?=?fastNode->next->next; ????????????slowNode?=?slowNode->next; if?(fastNode?==?slowNode) ????????????{ slowNode = head; while(fastNode?!=?slowNode ) ????????????????{ ????????????????????fastNode?=?fastNode->next; ????????????????????slowNode =?slowNode ->next; ????????????????} return?fastNode; ????????????} ????????} return?NULL; ????} }; ```