鏈表相關(guān)題

141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space? （Easy）

?

分析：

采用快慢指針，一個走兩步，一個走一步，快得能追上慢的說明有環(huán)，走到nullptr還沒有相遇說明沒有環(huán)。

代碼：

1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 bool hasCycle(ListNode *head) { 12 if (head == NULL) { 13 return 0; 14 } 15 ListNode* slow = head; 16 ListNode* fast = head; 17 while (fast != nullptr && fast->next != nullptr) { 18 slow = slow->next; 19 fast = fast->next->next; 20 if (slow == fast) { 21 return true; 22 } 23 } 24 return false; 25 } 26 };

?

142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return?null.

Note:?Do not modify the linked list.

Follow up:
Can you solve it without using extra space?（Medium）

?

分析：

1）同linked-list-cycle-i一題，使用快慢指針方法，判定是否存在環(huán)，并記錄兩指針相遇位置(Z)； 2）將兩指針分別放在鏈表頭(X)和相遇位置(Z)，并改為相同速度推進，則兩指針在環(huán)開始位置相遇(Y)。 證明如下： 如下圖所示，X,Y,Z分別為鏈表起始位置，環(huán)開始位置和兩指針相遇位置，則根據(jù)快指針速度為慢指針速度的兩倍，可以得出： 2*(a + b) = a + b + n * (b + c)；即 a=(n - 1) * b + n * c = (n - 1)(b + c) +c; 注意到b+c恰好為環(huán)的長度，故可以推出，如將此時兩指針分別放在起始位置和相遇位置，并以相同速度前進，當一個指針走完距離a時，另一個指針恰好走出 繞環(huán)n-1圈加上c的距離。 故兩指針會在環(huán)開始位置相遇。 代碼： 1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 class Solution { 10 public: 11 ListNode *detectCycle(ListNode *head) { 12 if(head == nullptr) { 13 return 0; 14 } 15 ListNode* slow = head; 16 ListNode* fast = head; 17 while (fast != nullptr && fast->next != nullptr) { 18 slow = slow -> next; 19 fast = fast -> next -> next; 20 if(slow == fast){ 21 break; 22 } 23 } 24 if (fast == nullptr || fast->next == nullptr) { 25 return nullptr; 26 } 27 slow = head; 28 while (slow != fast) { 29 slow = slow->next; 30 fast = fast->next; 31 } 32 return slow; 33 } 34 };

?

轉(zhuǎn)載于:https://www.cnblogs.com/wangxiaobao/p/6188596.html

總結(jié)

以上是生活随笔為你收集整理的LeetCode141 Linked List Cycle. LeetCode142 Linked List Cycle II的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。