# Linked List Cycle - Two Pointers / Cycle Finding

we can do this with one pointer but using hash which increases the space complexity to O(N):
“”"
:rtype: bool
“”"
visited = set()
while node:
if node in visited:
return True
else:
node = node.next

``````    return False
``````

However, a set is not constant memory, and there might be issues with hashing and whatnot.

Why is my code incorrect? Can anyone pls help!

My JS solution works on leetcode, but it doesn’t pass here.

``````const hasCycle = (nodes) => {
let t = nodes
let h = nodes

while (h && h.next) {
t = t.next;
h = h.next.next;
if (t == h) return true;
}
return false;
}
``````

def has_cycle(nodes: Node) → bool:
# WRITE YOUR BRILLIANT CODE HERE
if nodes is None:
return False

``````slow = nodes
fast = nodes.next

while slow != fast:
if fast is None or fast.next is None:
return False
slow = slow.next
fast = fast.next.next

return True
``````

Heads up, the Javascript setup code (`buildList` function) for this problem is broken. As it currently stands, it doesn’t actually create any cycles and thus every test case returns `false` incorrectly, even for a valid solution (like the one Kelsey posted). When I looked into the other languages (Python and Java), I noticed they were all handling a `!= -1` case that the Javascript code was not and also linking nodes not via their order, but by the number within the input list.

To fix the setup code to replicate the other languages, I updated the `buildList` as follows:

``````function buildList(nodes) {
const rawList = Array.from(nodes).map(Number);

const nodeList = [];
for (let i = 0; i < rawList.length; i++) {
nodeList.push(new Node(i));
}

for (let i = 0; i < rawList.length; i++) {
if (rawList[i] != -1) {
nodeList[i].next = nodeList[rawList[i]];
}
}

return nodeList;
}
``````

This doesn’t follow the original recursive strategy, but at least mimics the setup logic from the other languages and allows the valid code from Kelsey to correctly pass all test cases.

``````slow = fast = nodes

while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
``````

Same exact solution, bar the while condition which should also consider fast having reached the end of the list (None) in which case you would basically hit an error for trying to access None.next

Way less complicated code:

``````public static boolean hasCycle(Node<Integer> nodes) {

Node<Integer> slow = nodes;
Node<Integer> fast = nodes.next;

while (fast.next != null && fast.next.next != null) {

if (slow == fast) return true;
slow = slow.next;
fast = fast.next.next;

}

return false;
}
``````

the above solution considers that case: fast is None when the end of linked list is reached so the loop would be interrupted and False is returned

``````def has_cycle(nodes: Node) -> bool:
slow = fast = nodes
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
``````

while nodes:
if nodes.val < 0:
return True
nodes.val *=-1
nodes=nodes.next
return False

‘’’
private static Node nextNode(Node node) {
if (node.next == null)
return node;
return node.next;
}

``````public static boolean hasCycle(Node<Integer> nodes) {
Node<Integer> tortoise = nextNode(nodes);
Node<Integer> hare = nextNode(nextNode(nodes));

while (hare != tortoise && hare.next != null) {
tortoise = nextNode(tortoise);
hare = nextNode(nextNode(hare));
}

return hare == tortoise;
}
``````

Here’s an alternative solution in Python:

``````def has_cycle(nodes: Node) -> bool:
slow = nodes
fast = nodes
while fast and fast.next:
fast = fast.next.next
slow = slow.next
if fast == slow:
return True
return False
``````

Java version:

``````public static boolean hasCycle(Node<Integer> nodes) {
if (nodes == null)
return false;

Node<Integer> slow = nodes;
Node<Integer> fast = nodes;

while(fast != null && fast.next != null){ // if fast!=null, slow!=null for sure, as slow is much slower than fast
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
return true;
}
}

return false;
}
``````
``````def has_cycle(nodes: Node) -> bool:
"""
1. have a fast and slow pointer
2. the fast pointer moves by 2 and the slow moves by 1
3. if the fast and slow equal then there is a cycle
4. if fast reaches null then we do not have a cycle
"""
fast = nodes
slow = nodes
while fast and fast.next is not None:
fast = fast.next.next
slow = slow.next
if fast and fast == slow:
return True
return False
``````