Detect and Remove Loop in a Linked List

Detect and Remove Loop in a Linked List

#!/usr/bin/env python
# -*- coding: utf-8 -*-

# Question.
# Detect and Remove Loop in a Linked List
# Write a function detectAndRemoveLoop() that checks whether a given Linked List contains loop and
# if loop is present then removes the loop and returns true. And if the list doesn’t contain loop
# then returns false. Below diagram shows a linked list with a loop. detectAndRemoveLoop() must change
# the below list to 1->2->3->4->5->NULL.

import time

class Node:
  def __init__(self, value, next=None):
    self.value = value
    self.next_ptr = next

  def __str__(self):
    return "%d" % (self.value)

class LinkedList:
  def __init__(self):
    self.edge_node = None

  def add_node(self, node):
    self.edge_node = node

  def add(self, node_value):
    new_node = Node(node_value, self.edge_node)
    self.add_node(new_node)

    return new_node

  def _detect_loop(self):
    turtle_node = rabbit_node = self.edge_node
    print ">> Start detecting"
    while True:
      turtle_node = turtle_node.next_ptr
      rabbit_node = rabbit_node.next_ptr.next_ptr
      print "turtle_node: %s" % turtle_node
      print "rabbit_node: %s" % rabbit_node
      if turtle_node == rabbit_node or not turtle_node.next_ptr or not rabbit_node.next_ptr:
        break
    print ">> End detecting"
    if turtle_node == rabbit_node:
      return  turtle_node
    else:
      return None

  def _delete_loop(self, loop_end_node):
    loop_end_node.next_ptr = None

  def detect_and_remove_loop(self):
    loop_end_node = self._detect_loop()
    if loop_end_node:
      self._delete_loop(loop_end_node)
      return True
    else:
      return False

  def __str__(self):
    node_value_arr = []
    node = self.edge_node
    while node:
      node_value_arr.append(str(node))
      node = node.next_ptr

    return "\n".join(node_value_arr)

if __name__ == '__main__':
  # Setup linkedlist
  linked_list = LinkedList()

  node_5 = linked_list.add(5)
  node_4 = linked_list.add(4)
  node_3 = linked_list.add(3)
  node_2 = linked_list.add(2)
  node_1 = linked_list.add(1)

  # Make loop
  node_5.next_ptr = node_2

  start_time = time.time()
  print "BEFORE start to run detect_and_remove_loop: node_5 : %s" % node_5.next_ptr
  result = linked_list.detect_and_remove_loop()
  print "AFTER start to run detect_and_remove_loop: node_5 : %s" % node_5.next_ptr
  elapsed_time = time.time() - start_time
  print ("RESULT : Loop detected and removed" if result else "No loop")
  print ("Elapse Time : %f" % elapsed_time)