DIR Return Create A Forum - Home
       ---------------------------------------------------------
       techsuns
  HTML https://techsuns.createaforum.com
       ---------------------------------------------------------
       *****************************************************
   DIR Return to: Puzzles && Algorithms
       *****************************************************
       #Post#: 10--------------------------------------------------
       Linked List
   DIR By: kranthipls
       Date: August 9, 2012, 10:18 am
       ---------------------------------------------------------
       Given a linked list how do you find if the linked list consists
       of a loop
       Loop: Loop means the last node is connected back again to one of
       the nodes in the whole list.
       #Post#: 11--------------------------------------------------
       Re: Linked List
   DIR By: dinesh
       Date: August 12, 2012, 1:05 am
       ---------------------------------------------------------
       Use two pointers: hare and tortoise pointers. If there is a
       loop, ultimately they will point to the same node.
       Can anyone throw some light on the guarantee of convergence and
       how long it will take to converge?
       What is the complexity of this algorithm?
       #Post#: 277--------------------------------------------------
       Re: Linked List
   DIR By: kranthipls
       Date: November 30, 2012, 2:12 am
       ---------------------------------------------------------
       @Dinesh since no one has answered could you please answer the
       above question...........
       #Post#: 278--------------------------------------------------
       Re: Linked List
   DIR By: dinesh
       Date: November 30, 2012, 3:12 am
       ---------------------------------------------------------
       The algorithm is called Floyd's Cycle-Finding Algorithm aka The
       Tortoise and the Hare Algorithm. It has O(n) complexity. (also
       called  Turtle and Rabbit algorithm)
       int *head = list.GetHead();
       if (head != null) {
       int *fastPtr = head;
       int *slowPtr = head;
       bool isCircular = true;
       do
       {
       if (fastPtr->Next == null || fastPtr->Next->Next ==
       null) //List end found
       {
       isCircular = false;
       break;
       }
       fastPtr = fastPtr->Next->Next;
       slowPtr = slowPtr->Next;
       } while (fastPtr != slowPtr);
       //Do whatever you want with the 'isCircular' flag here
       }
  HTML http://en.wikipedia.org/wiki/Floyd%27s_cycle-finding_algorithm#Tortoise_and_hare
       #Post#: 285--------------------------------------------------
       Re: Linked List
   DIR By: kranthipls
       Date: November 30, 2012, 9:56 am
       ---------------------------------------------------------
       @Dinesh you just gave the complexity.......What about the
       convergence
       *****************************************************
       Page 1 of 1