linked list cycle ii

这道题解法已经写过很多遍了,要理解的是证明的过程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class (object):
def detectCycle(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head:
return None
slow = head
fast = head
found = False
counter = 0
while fast and fast.next:
if counter != 0:
if slow is fast:
found = True
break
slow = slow.next
fast = fast.next.next
counter += 1
if found:
slow = head
while slow and fast:
if slow is fast:
return slow
else:
slow = slow.next
fast = fast.next
else:
return None