Thursday, June 12, 2014

LeetCode (Python): Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return 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