Detecting Cycles in Linked List (Hare and Tortoise)

The problem is as follows:
Check whether the given linked list is NULL terminated or ends in a cycle.

Sample Input: 1->2->3->4->5->6->7->8->3
where the numbers 1,2… are the positions in the linked list instead of actual entries.
The node at the 8th position again points to the node at the 3rd position forming a cycle.

Sample Output: True

A very good discussion of how the cycles are detected can be found in wikipedia over here:http://en.wikipedia.org/wiki/Cycle_detection

The Floyds’ algorithm commonly referred as tortoise and hare method is often used for detecting cycles. It could be an interesting read.

We can think of a hare and a tortoise running on a track. The faster running hare will catch up with the tortoise if they are running in a loop.

The basic algorithm is as follows:
Step 1. Start Tortoise and Hare at the first node of the List.
Step 2. If Hare reaches end of the List, return as there is no loop in the list.
Else move Hare one step forward.
Step 3. If Hare reaches end of the List, return as there is no loop in the list.
Else move Hare and Tortoise one step forward.
Step 4. If Hare and Tortoise pointing to same Node return, we found loop in the List.
Else start with STEP-2.

'''Complexity
Space : O(n) Time: O(1)'''


class Node:
    def __init__(self,data):
        self.data = data
        self.next = None
        
    def setData(self,data):
        self.data = data
    
    def getData(self):
        return self.data
    
    def setNext(self, next):
        self.next = next
        
    def getNext(self):
        return self.next
    
    
class LinkedList:
    def __init__(self):
        self.head = None
        
    def isEmpty(self):
        return self.head == None
    
    def insertAtBeg(self,item):
        node = Node(item)
        node.setNext(self.head)
        self.head = node
        
    def length(self):
        current = self.head
        count = 0
        while current != None:
            count += 1
            current = current.getNext()
        return count
    
    def search(self,item):
        found = False
        current = self.head
        while current != None and not found:
            if current.getData() == item:
                found = True
            else:
                current = current.getNext()
                
        return found
    
    def insertAtEnd(self,item):
        current = self.head
        
        while current.getNext() != None:
            current = current.getNext()
            
        node = Node(item)
        current.setNext(node)
        
    def insertBeforeItem(self,inItem,item):
        current = self.head
        previous = None
        found = False
        stop = False
        
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
                stop = True
            else:
                previous = current
                current = current.getNext()
                
        node = Node(inItem)
        previous.setNext(node)
        node.setNext(current)
        
        
    def insertAfterItem(self,inItem,item):
        current = self.head
        
        found = False
        stop = False
        
        while current != None and not found and not stop:
            if current.getData() == item:
                found = True
                stop = True
            else:
#                previous = current
                current = current.getNext()
        successor = current.getNext()       
        node = Node(inItem)
        current.setNext(node)
        node.setNext(successor)
        
            
        
        
        
    def printList(self):
        current = self.head
        
        while current != None:
            print current.getData()
            current = current.getNext()
            
            
    def remove(self,item):
        found = False
        current = self.head
        previous = None
        
        while current.getNext() != None and not found:
            if current.getData() == item:
                print current.getData()
                print previous.getData()
                found = True
                previous.setNext(current.next)
            else:
                previous = current
                current = current.getNext()
                
    def induceCycle(self,end,start):
        current = self.head
        stop = False
        endnodeFound = False
        endnodePointer = None
        count = 0
        while current!= None and not stop:
            count += 1
            if count == end:
                endnodeFound = True
                endnodePointer = current.getNext()
                
            else:
                if count == start:
                    stop = True
                else:
                    current = current.getNext()
                    
        current.setNext(endnodePointer)
        
    def detectCycle(self):
        hare = self.head
        tortoise = self.head
        
        while (hare and tortoise):
            hare = hare.getNext()
            if (hare == tortoise):
                return True
            
            if hare == None:
                return False
            
            hare = hare.getNext()
            if (hare == tortoise):
                return True
            
            tortoise = tortoise.getNext()
            
        
        
        
                
        
        
            
        
        
if __name__ == "__main__":
    ll = LinkedList()
    ll.insertAtBeg(1)
    ll.insertAtBeg(2)
    ll.insertAtEnd(3)
    ll.insertBeforeItem(4, 3)
    ll.insertAfterItem(5, 1)
    ll.insertAtEnd(6)
    ll.insertAtEnd(8)
    ll.insertAtEnd(7)
    
    
    ll.printList()
    
    ll.induceCycle(2, 8)
    print ll.detectCycle()

Advertisements