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.