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
).