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?
題解：
本題要求的是鏈表中存在的環(huán)的入口節(jié)點(diǎn)向叉，如果不存在環(huán)吏颖，則返回NULL呢岗；
兩種方法：
第一種方法很簡(jiǎn)單济蝉，使用集合set茵汰，每次在set中查找節(jié)點(diǎn)是否已存在瘾英，如果沒(méi)有浩村，將鏈表中節(jié)點(diǎn)存入set中露戒，如果存在描验，則說(shuō)明該位置為環(huán)的起始節(jié)點(diǎn)白嘁；
下面我們?cè)敿?xì)介紹下第二種方法，快慢指針膘流；
如圖：我們用fast表示快指針絮缅，每次移動(dòng)兩步；slow表示慢指針呼股，每次移動(dòng)一步耕魄；圖中f1，s1分別對(duì)應(yīng)著第一次移動(dòng)是快慢指針移動(dòng)后所指向的位置彭谁；可以看到吸奴，當(dāng)快慢指針移動(dòng)到第五步（f5，s5）時(shí)缠局，他們相遇了奄抽；下面我們來(lái)分析下快慢指針相遇前經(jīng)過(guò)的節(jié)點(diǎn)：
slow：節(jié)點(diǎn)1->2->3->4->5->6
fast：節(jié)點(diǎn)1->2->3->4->5->6->7->3->4->5->6
由于slow每次移動(dòng)一步，fast每次移動(dòng)兩步甩鳄，所以不難得出：
fast = 2*slow
所以得到：
(1->2->3->4->5->)6, 1->2->3(->4->5->6) =
(1->2->3->4->5->)6->7->3(->4->5->6)
刪除帶括號(hào)的重復(fù)部分逞度，最終得到：
1->2->3 = 6->7->3
進(jìn)行到這里，我們可以得出介樣一個(gè)結(jié)論妙啃，辣就是從頭結(jié)點(diǎn)（1）到環(huán)的起始節(jié)點(diǎn)（3）的距離等同于從快慢指針相遇的結(jié)點(diǎn)（6）到環(huán)的起始節(jié)點(diǎn)（3）的距離５翟蟆！
最后給出快慢指針的C++實(shí)現(xiàn)以及set的Python實(shí)現(xiàn)：
My Solution1（C/C++完整實(shí)現(xiàn)）：
#include <cstdio>
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode *next;
ListNode(int x): val(x), next(NULL) {}
};
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
ListNode *slow = head;
ListNode *fast = head;
ListNode *meet = NULL;
while(fast) {
slow = slow->next;
fast = fast->next;
if(!fast) {
return NULL;
}
fast = fast->next;
if(fast == slow) {
meet = fast;
break;
}
}
while(meet) {
if(head == meet) {
return head;
}
meet = meet->next;
head = head->next;
}
return NULL;
}
};
int main() {
ListNode a(1);
ListNode b(2);
ListNode c(3);
ListNode d(4);
ListNode e(5);
ListNode f(6);
ListNode g(7);
a.next = &b;
b.next = &c;
c.next = &d;
d.next = &e;
e.next = &f;
f.next = &g;
g.next = &c;
Solution s;
ListNode *result = s.detectCycle(&a);
printf("%d\n", result->val);
return 0;
}
結(jié)果：
3
Process returned 0 (0x0) execution time : 0.023 s
Press any key to continue.
My Solution2（Python）：
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
s = set('')
while head:
if head not in s:
s.add(head)
else:
return head
head = head.next
return None
