Sign InCoursewareNuggetsTutorials AboutClassesCodePad

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.

Linked List with Loop
class Node: def __init__(self, data, next=None): = data = next class LinkedList: def __init__(self, head=None): self.head = head def insert(self, new_data): new_node = Node(new_data) = 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 = 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.display() # Oops! The list has a loop.
© CS Wonders·About·Classes·Cheatsheet