Linked List Cycle II · 數據結構與算法/leetcode/lintcode題解

# Linked List Cycle II ### Source - leetcode: [Linked List Cycle II | LeetCode OJ](https://leetcode.com/problems/linked-list-cycle-ii/) - lintcode: [(103) Linked List Cycle II](http://www.lintcode.com/en/problem/linked-list-cycle-ii/) ~~~ Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Example Given -21->10->4->5, tail connects to node index 1，return node 10 Challenge Follow up: Can you solve it without using extra space? ~~~ ### 題解 - 快慢指針題 [Linked List Cycle | Data Structure and Algorithm](http://algorithm.yuanbin.me/zh-cn/linked_list/linked_list_cycle.html) 的升級版，題目要求不適用額外空間，則必然還是使用快慢指針解決問題。首先設組成環的節點個數為 rrr, 鏈表中節點個數為 nnn. 首先我們來分析下在鏈表有環時都能推出哪些特性： 1. 快慢指針第一次相遇時快指針比慢指針多走整數個環, 這個容易理解，相遇問題。 1. 每次相遇都在同一個節點。第一次相遇至第二次相遇，快指針需要比慢指針多走一個環的節點個數，而快指針比慢指針多走的步數正好是慢指針自身移動的步數，故慢指針恰好走了一圈回到原點。從以上兩個容易得到的特性可知，在僅僅知道第一次相遇時的節點還不夠，相遇后如果不改變既有策略則必然找不到環的入口。接下來我們分析下如何從第一次相遇的節點走到環的入口節點。還是讓我們先從實際例子出發，以下圖為例。 ![Linked List Cycle II](https://box.kancloud.cn/2015-10-24_562b1f4ae20b6.png) `slow`和`fast`節點分別初始化為節點`1`和`2`，假設快慢指針第一次相遇的節點為`0`, 對應于環中的第`i`個節點 CiC_iCi, 那么此時慢指針正好走了 n?r?1+in - r - 1 + in?r?1+i 步，快指針則走了 2?(n?r?1+i)2 \cdot (n - r - 1 + i)2?(n?r?1+i) 步，且存在[1](#): n?r?1+i+1=l?rn - r - 1 + i + 1= l \cdot rn?r?1+i+1=l?r. (之所以在`i`后面加1是因為快指針初始化時多走了一步) 快慢指針第一次相遇時慢指針肯定沒有走完整個環，且慢指針走的步數即為整數個環節點個數，由性質1和性質2可聯合推出。現在分析下相遇的節點和環的入口節點之間的關聯，要從環中第`i`個節點走到環的入口節點，則按照順時針方向移動[2](#): (l?r?i+1)(l \cdot r - i + 1)(l?r?i+1) 個節點 (lll 為某個非負整數) 即可到達。現在來看看式[1](#)和式[2](#)間的關系。由式[1](#)可以推知 n?r=l?r?in - r = l \cdot r - in?r=l?r?i. 從頭節點走到環的入口節點所走的步數可用 n?rn - rn?r 表示，故在快慢指針第一次相遇時讓另一節點從頭節點出發，慢指針仍從當前位置迭代，第二次相遇時的位置即為環的入口節點！ ****> 由于此題快指針初始化為頭節點的下一個節點，故分析起來稍微麻煩些，且在第一次相遇后需要讓慢指針先走一步，否則會出現死循環。對于該題來說，快慢指針都初始化為頭節點會方便很多，故以下代碼使用頭節點對快慢指針進行初始化。 ### C++ ~~~ /** * Definition of ListNode * class ListNode { * public: * int val; * ListNode *next; * ListNode(int val) { * this->val = val; * this->next = NULL; * } * } */ class Solution { public: /** * @param head: The first node of linked list. * @return: The node where the cycle begins. * if there is no cycle, return null */ ListNode *detectCycle(ListNode *head) { if (NULL == head || NULL == head->next) { return NULL; } ListNode *slow = head, *fast = head; while (NULL != fast && NULL != fast->next) { fast = fast->next->next; slow = slow->next; if (slow == fast) { fast = head; while (slow != fast) { fast = fast->next; slow = slow->next; } return slow; } } return NULL; } }; ~~~ ### 源碼分析 1. 異常處理。 1. 找第一次相遇的節點。 1. 將`fast`置為頭節點，并只走一步，直至快慢指針第二次相遇，返回慢指針所指的節點。 ### 復雜度分析第一次相遇的最壞時間復雜度為 O(n)O(n)O(n), 第二次相遇的最壞時間復雜度為 O(n)O(n)O(n). 故總的時間復雜度近似為 O(n)O(n)O(n), 空間復雜度 O(1)O(1)O(1). ### Reference - [Linked List Cycle II | 九章算法](http://www.jiuzhang.com/solutions/linked-list-cycle-ii/)