linkedlist/detect_loop.py at master · panvalkar1994/linkedlist · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from LinkedList import create_list, Node, print_list

l1 = create_list(list('ABCDEFGH'))
print_list(l1)

def create_loop_in_list(head:Node, pos:int):
    cur = head

    while cur.next is not None:
        cur = cur.next

    n = head
    for i in range(pos):
        if n is None:
            raise Exception("Invalid position provided")
        n = n.next
    cur.next = n

    return head

loop = create_loop_in_list(l1, 2)

# print loop
# for i in range(20):
#     print(loop.data, end="->")
#     loop = loop.next
# print()

def detect_loop(head:Node):
    if head is None or head.next is None:
        return False
    fast = head.next.next
    slow = head
    while fast and slow:
        if fast == slow:
            return True
        if fast.next is None:
            return False
        fast = fast.next.next
        slow = slow.next
    return False

print(detect_loop(l1))