Tortoise and hare algorithm, without extra space


  • 0
    Z

    Do not use the hash map, you only need two pointers, used for "the tortoise and the hare" algorithm. You can refer to my home page doc for detail explanation and proof to solve following three problems:

    1. Detect if there exists a cycle in the list;

    2. Length of the cycle

    3. The beginning node of the cycle

    Thanks


  • 0
    U

    If you figured out the algorithm by yourself, congratulations! You are really smart. I read it from an interview book. Basically let the hare run twice fast as the tortoise. If the start point is p steps away from the entrance of the cycle, then they will meet exactly p steps away towards the entrance in the cycle. Here is an python implementation:

    class Solution:
        # @param head, a ListNode
        # @return a list node
        def detectCycle(self, head):
            p1, p2 = head, head
            while p2 and p2.next:
                p2 = p2.next.next
                p1 = p1.next
                if p2 == p1:
                    while head != p1:
                        head = head.next
                        p1 = p1.next
                    return head

  • 0
    J

    I am wonder in what case the 'i' in 'x = μ + in + k' is larger than 0 ? Is it always 0 ? In other word, when slower pointer was caught by faster pointer, the slower pointer should have not finished a whole loop.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.