Oleksandr Gavenko's blog
2017-01-21 21:00 Find a loop in linked list

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

interview, problem ## Feeds

all / emacs / java

## Tags

adb(1), admin(1), android(1), anki(1), ansible(2), blog(2), c(1), css(2), cygwin(2), driver(1), emacs(3), fs(1), git(3), google(1), gradle(1), hardware(1), hg(2), html(1), interview(13), java(3), js(3), lang(2), lighttpd(1), markdown(1), mobile(1), naming(1), oracle(1), print(1), problem(5), python(1), quiz(6), rst(2), security(3), spring(1), sql(2), srs(1), style(1), tls(2), txt(1), unit(1), utils(1), vcs(3), web(2), win(2), windows(1)