Detecting Loop in a Linked List
Given a linked list, check if it has a loop or not. Return True if a loop is detected. Below diagram shows a linked list with a loop.
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class LinkedList:
def __init__(self, head=None):
self.head = head
def insert(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def detectLoop(self):
# Returns True if this list has a loop.
#TODO: Your code goes here.
def display(self):
current = self.head
# If a loop is detected, return.
if self.detectLoop():
print("Oops! The list has a loop.")
return
tmp_list = []
while current:
tmp_list.append(current.data)
current = current.next
print(tmp_list)
# Testing
# Create a linked list.
test_list = LinkedList()
test_list.insert(4)
test_list.insert(3)
test_list.insert(2)
test_list.insert(1)
test_list.display() # [1, 2, 3, 4]
# Make a loop in the list.
test_list.head.next.next.next.next = test_list.head.next.next
test_list.display() # Oops! The list has a loop.