Linked List Cycle - Two Pointers / Cycle Finding

Problems
1

https://algo.monster/problems/linked_list_cycle

2

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

    return False
3

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

4

Why is my code incorrect? Can anyone pls help!

6

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

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
8

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[0];
}

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.

10 
slow = fast = nodes

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

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

12

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;
}
13

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

14 
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
15

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

16

‘’’
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;
}
17

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
18

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; 
}
19 
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