/* Ajith - Syntax Higlighter - End ----------------------------------------------- */

12.25.2012

Detecting First Node in a Loop in the List

This article is part of article series - "Datastructures"

Previous Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.
Next Article: Finding Nth node from end of a Singly Linked List.

Once we confirm that there is a Loop in a Singly Linked List we will see how to determine first node of the loop.



Figure-1: Singly Linked list with a loop which we have detected using Floyd's Cycle Detection Algorithm

NOTE: Example in Figure-1 is the output of Floyd's Cycle detection Algorithm which we have seen in Floyd's Cycle Detection Algorithm. We are not randomly choosing Hare and Tortoise at Node-6.

Solution 01: Brute-force Approach
  1. Start at the Head of the Singly Linked List (i.e. curNode).
  2. If Tortoise and Hare are at the same Node move the curNode forward by one position.
  3. If Tortoise and curNode are at the same Node return, we have found first Node in the loop.
  4. Move Tortoise forward by one position and start with STEP-2.
Pseudocode:
curNode = head

forever:

  if tortoise == hare
    tortoise = tortoise.next
    curNode = curNode.next

  if tortoise == curNode
    return curNode

  tortoise = tortoise.next 
Complexity:
  • Time Complexity: O(n*p) - where 'p' is the length of the loop and 'n' is the length of the List.
  • Space Complexity: O(1)

Example:

Let us try above algorithm on example in Figure-1.The pattern for Hare, Tortoise and Culprit is given below

Hare  Tortoise  Culprit
7          7            HEAD
7          8            1
7          3            1
7          4            1
7          5            1
7          6            1
7          7            1
7          8            2
7          3            2
7          4            2
7          5            2
7          6            2
7          7            2
7          8            3
7          3            3


Solution 02:

Let use see how to improve the Time Complexity of the solution 01.

But before we go into the solution I would like to mention that the below solution can be used only after detecting a loop in the singly linked list. As mentioned Figure-1 is the output of Floyd's cycle detection algorithm and we havent randomly choosen Node-7. As pointed out many users if we start from Node-6 we might end up in loop.
  1. Start Tortoise at first node.
  2. Move Hare and Tortoise by one position.
  3. If Hare and Tortoise points to same node then return (its the first Node in the loop)
  4. Start again from STEP-2

Pseudocode:
tortoise := firstNode

forever:

  if tortoise == hare
    return tortoise

  tortoise := tortoise.next
  hare := hare.next
Complexity:
  • Time Complexity: O(n)
  • Space Complexity: O(1)

Example:

Let us try above algorithm on same example in Figure-1. Now let us start the Tortoise from the first node in the list.


The pattern for Hare and Tortoise is given below

Hare  Tortoise
7          1       
8          2       
3          3       


Previous Article: Detecting a Loop in Singly Linked List - Tortoise and Hare.
Next Article: Finding Nth node from end of a Singly Linked List.

2 comments :

  1. In the 'improved' algorithm, what stops the tortoise and hare from both cycling indefinitely if they don't happen to hit the first time? Like if the hare had started at 6 instead of 7?

    ReplyDelete
    Replies
    1. Sorry I guess you missed out the NOTE mentioned at the start of the program. If I am randomly picking the node as 6 instead of 7 then YES in that you will land in a Loop.

      But in the above example I havent picked it randomly but it is the output for floyd's cycle detection algorithm. I would update the solution same so that others will not be confused.

      Delete

Your comments are moderated