Sign InNuggetsCoursesCodePadCheatsheet

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): 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.
© CS Wonders·Home·About·Contact·Classes·Gallery·Glossary·Fun Facts