null.
Follow up:
Can you solve it without using extra space?
Solution:
We first detect if a cycle exists, as Linked List Cycle I. Then we keep a pointer in the same position and obtain the length of the loop. With that we just have to keep the fast pointer this amount of positions in advance and they will always cross where the cycle starts.# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
# @param head, a ListNode
# @return a list node
def detectCycle(self, head):
if head == None or head.next == None:
return None
slowPointer = head
fastPointer = head.next
while fastPointer !=None and fastPointer.next!= None and fastPointer != slowPointer:
fastPointer = fastPointer.next.next
slowPointer = slowPointer.next
if fastPointer != slowPointer:
return None
cycleSize = 1
fastPointer = fastPointer.next
while fastPointer != slowPointer:
fastPointer = fastPointer.next
cycleSize += 1
fastPointer = head
for i in xrange(0,cycleSize):
fastPointer = fastPointer.next
slowPointer = head
while fastPointer != slowPointer:
fastPointer = fastPointer.next
slowPointer = slowPointer.next
return fastPointer
No comments :
Post a Comment