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