Different approach to detecting cycle/loop in a linked list

Question

So I know about Floyd's cycle detection algorithm but while going over the problem I came up with another idea to solve it.

If we can store the 'nextpointer' of every node in a vector/list while we traverse the linked list and the count if the frequency of any element is more than 1 or not. If any value in the vector/list occurs more than once, it basically means that a single node has been pointed to twice(or more) and hence, it becomes a cycle.

I couldn't manage to code the same in Python 3. would really appreciate if y'all could help me out. Thanks.

class Node:
    head = None

    def __init__(self, data=None, nextnode=None):
        self.data = data
        self.next = nextnode

def findMergeNode(head1, head2):
    a = set()
    b = set()
    while (head1 and head2):
        a.add(head1)
        head1 = head1.next        
        b.add(head2)
        head2 = head2.next
    if (a.intersection(b)):
        return a.intersection(b)

Answer 1

Your proposed algorithm will work, but

1. It requires O(n) space, and
2. A lookup in a list (vector) requires O(n) time

The second can be solved by using a set instead, but the first remains a major downside.

Here is a bare bones implementation with a set:

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next

    def add(self, val):
        self.next = Node(val)
        return self.next  # to allow chaining

    def hascycle(self):
        node = self
        visited = set()
        while node:
            if node in visited:  # been here before!
                return True
            visited.add(node)
            node = node.next
        return False

# Demo graph: a -> b -> c -> d -> e -> b
a = Node("a")
e = a.add("b").add("c").add("d").add("e")
# make a back reference from e to b:
e.next = a.next
print(a.hascycle())  # True

Note how the size of visited can become of the same order of magnitude as the linked list itself. Certainly when no cycle is detected, references to all nodes are stored in the set.

The beauty of Floyd's algorithm is that it uses constant space only (not counting the list itself of course). So independent of the size of the linked list, it will always use the same amount of space to operate.