ID: 142; medium

## Solution 1 (Go)

/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
m := make(map[*ListNode]bool)
if _,found := m[head]; found {
}
}
return nil
}

## Solution 2 (Go)

/**
* type ListNode struct {
*     Val int
*     Next *ListNode
* }
*/
return nil
}
// both move by 1 and look for second meet
for tortoise != hare {
tortoise = tortoise.Next
hare = hare.Next
}
}

// from ID: 141
func hasCycle(head *ListNode) (bool, *ListNode) {
for tortoise != nil && hare != nil && hare.Next != nil {
tortoise = tortoise.Next
hare = hare.Next.Next
if tortoise == hare {
return true, tortoise
}
}
return false, nil

}

## Solution 3 (Java)

/**
* Definition for ListNode
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/

public class Solution {
/**
* @return: The node where the cycle begins. if there is no cycle, return null
*/
return null;

// slow and fast meet for the first time
while (slow != fast) {
if (fast == null || fast.next == null)
return null;
slow = slow.next;
fast = fast.next.next;
}

// the second meeting point is the start of the cycle
fast = fast.next;
fast = fast.next;
}
}

}

We first use the same algorithm (modified to return the first meeting point) for problem ID: 141. If there is no cycle, we are done and return null. If there is a cycle, we store the first meeting point. From this first meeting point, we set the speed of both the tortoise and the hare to moving by 1 each time. Eventually, they will meet again at the start of the cycle. A quick proof is as follows:

Let x be the distance between the head and the start of the cycle, y be the distance between the start of the cycle to the first meeting point, z be the distance between the first meeting point to the start of the cycle. It is clear that y + z = n, where n is the length of the cycle. Consider the following equations for their first meet:

$t_{tortoise} = \frac{x+y}{1}, \hspace{0.2cm} t_{hare} = \frac{x+y+z+y}{2}$

Because they meet at the first meeting point, their time spent traveling should be the same. Setting the two t's equal to each other, we have x = z.

Using this result, we have either one of them start at the head of the list and the other continue at their first meeting point (with the same speed now). They will eventually meet at the start of the cycle thanks to the fact x = z.

Last updated