Today I'll show how to find a loop in linked list with a linear time complexity.

Assume that we have singly linked list:

class List: def __init__(self, value = None, next = None): self.value = value self.next = next

To find loop in a list we will use two pointers that moves with different speed until they become
equal or fast one becomes `None`

. First is incremented by one step, second is incremented by two
steps. They start from the beginning of a list with the fast one step ahead.

If there is a loop with length `len`

and loop begins from `off`

offset at some step `n`

we
will have slow and fast pointer in the same position:

slow: off + {(n - off) mod len} fast: off + {(1 + 2*n - off) mod len}

or:

n - off = 1 + 2*n - off (mod len) 1 + n = 0 (mod len) n = len - 1 (mod len)

which will happen after `len-1`

or `2*len-1`

or some `X*len-1`

step that is greater then
`off`

.

Our lists may look like:

Node1 -> Node2 -> None Node1 -> Node2 -> Node3 -> Node4 ^ | | | +----------------+

Solution is:

class List: def __init__(self, value = None, next = None): self.value = value self.next = next def visual(self, depth): buf = [] lst = self for _ in range(depth): buf.append(str(lst.value)) lst = lst.next if not lst: break return " -> ".join(buf) def find_loop(self): slow = self fast = self.next steps = 0 while fast is not None and fast.next is not None: print(slow.value, fast.value) if slow == fast: print("It takes: {} steps".format(steps)) return True slow = slow.next fast = fast.next.next steps += 1 return False def __repr__(self): if self.next: return "[List {} -> {} ->...]".format(self.value, self.next.value) else: return "[List {} -> None]".format(self.value) def create_loop_list(loop_start, loop_len): lst_end = List(0) lst = lst_end for n in range(1, loop_len): lst = List(n, lst) lst_end.next = lst for n in range(loop_len, loop_len+loop_start): lst = List(n, lst) return lst

Output from running:

LST = create_loop_list(6, 3) print(LST.visual(6+3+1)) print(LST.find_loop())

is:

8 -> 7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1 -> 0 -> 2 (8, 7) (7, 5) (6, 3) (5, 1) (4, 2) (3, 0) (2, 1) (1, 2) (0, 0) It takes: 8 steps True

From above formula it takes `8`

steps as the first number in form of `3*X - 1`

that is bigger than
`6`

(this is happened when `X=3`

).