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

    # def FromList(xs):
    #     # recursively construct a linked list from xs
    #     last = Node(xs[-1]) # last node in the linked list with no succesor
    #     nxt = last
    #     for i in range(len(xs)-1, 0, -1):
    #         nxt = Node(xs[i], nxt)
    #     return nxt

    def FromList(xs):
        if len(xs) == 0:
            return None
        else:
            return Node(xs[0], Node.FromList(xs[1:]))
    
    def getVal(self, n):
        if n == 0:
            return self.val
        if self.nxt == None:
            return None
        return self.nxt.getVal(n-1)
            

    def getNode(self,n):
        if n == 0:
            return self
        if self.nxt == None:
            return None
        return self.nxt.getNode(n-1)

example1 = Node.FromList([3,4,5,6,7,8,9])
example2 = Node.FromList([3,4,5,6,7,8,9])
example2.getNode(6).nxt = example2 # cycle: last points to first
example3 = Node.FromList([3,4,5,6,7,8,9])
example3.getNode(6).nxt = example3.getNode(4) # cycle: last points to 5th

[example1.getVal(i) for i in range(7)] # should be 3,4,5,6,7,8,9

[3, 4, 5, 6, 7, 8, 9]

[example2.getVal(i) for i in range(10)] # should be 3,4,5,6,7,8,9,3,4,5

[3, 4, 5, 6, 7, 8, 9, 3, 4, 5]

def find_cycles_bigspace(node):
    # do the O(n) space complexity thing
    seen = {node} # set of nodes that were already visited
    while node.nxt != None: # node is not the last one
        if node.nxt in seen: # O(1) time
            return node # found a node in cycle
        else: 
            seen.add(node)
            node = node.nxt
        
    return None # no node in cycle because no cycles
    
    

for eg in [example1,example2,example3]:
    print(find_cycles_bigspace(eg))

None
<__main__.Node object at 0x10873c160>
<__main__.Node object at 0x1086a20d0>

def find_cycles_const(node):
    # O(1) space complexity
    prev = node
    length = 1 # ruled out cycles shorter or equal to this by steady state
    while node.nxt != None: # node is not the last one
        for i in range(length):
            node = node.nxt
            if node == None:
                return None
            elif node == prev:
                return node
            i += 1

        prev = node
        length = 2*length
        
    return None # no node in cycle because no cycles

for eg in [example1,example2,example3]:
    print(find_cycles_const(eg))

None
<__main__.Node object at 0x1086959b0>
<__main__.Node object at 0x1083ee750>