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?
Solution
(Linked-List-Cycle2.py) download
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
| # 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
"""
if head == None or head.next == None:
return None
slow = head
fast = head
while fast.next!=None and fast.next.next != None:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if fast.next == None or fast.next.next==None:
return None
# find the start point
a = head
while a != fast:
a = a.next
fast = fast.next
return a
|