**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**

- Start at the Head of the Singly Linked List (i.e.
**curNode**). - If
**Tortoise**and**Hare**are at the same Node move the**curNode**forward by one position. - If
**Tortoise**and**curNode**are at the same Node return, we have found first Node in the loop. - 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.

- Start
**Tortoise**at first node. - Move
**Hare**and**Tortoise**by one position. - If
**Hare**and**Tortoise**points to same node then return (its the first Node in the loop) - 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.

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?

ReplyDeleteSorry 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.

DeleteBut 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.