# 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

## One thought on “Detecting Cycles in Linked List (Hare and Tortoise)”

1. Pingback: Linked Lists | codeatsociallywired