Fastest way to prove linked list is circular ? in python
algorithm, data-structures, linked-list, python
Solution
A good algorithm is as follows, it may very well be the best. You do not need to copy the list or anything, like that, it can be done in constant space.
Take two pointers and set them to the beginning of the list.
Let one increment one node at a time and the other two nodes at a time.
If there is a loop at any point in the list, they will have to be pointing to the same node at some point (not including the starting point). Obviously if you reach the end of the list, there is no loop.
EDIT: Your code, but slightly edited:
def is_circular(head):
slow = head
fast = head
while fast != None:
slow = slow.next
if fast.next != None:
fast = fast.next.next
else:
return False
if slow is fast:
return True
return False
Problem
Could someone please let me know the best way to prove a linked list contains a loop? I am using an algorithm with two pointer, one is moving slow with one steps and one is moving faster with two steps. ``` class Node(object): def __init__(self, value, next=None): self.next=next self.value=value def create_list(): last = Node(8) head = Node(7, last) head = Node(6, head) head = Node(5, head) head = Node(4, head) head = Node(3, head) head = Node(2, head) head = Node(1, head) last.next = head return head def is_circular(head): slow = head fast = head while True: slow = slow.next fast = fast.next.next print slow.value, fast.value if slow.value == fast.value: return True elif slow is fast: return False if __name__ == "__main__": node = create_list() print is_circular(node) ```