Oliver's Blog
Search…
⌃K

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;
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.