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()
Pingback: Linked Lists | codeatsociallywired