### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

In this problem, we are given a linked list with a loop. We have to find the first node of the loop in the linked list.

### Problem Statement Understanding

Letâ€™s try to understand the problem statement with the help of examples.

Suppose the given list is:

- According to the problem statement, we need to find the starting node of the loop.
- From the linked list, we can see that there is a loop in the linked list starting at node with value 3 and containing 3 nodes 3, 5, and 7. The last node of the loop points back to the first node of the loop.
- As node with value 3 is the first node of the loop, so we will return 3 as output.

If the given linked list is:

- In this case, our loop comprises 6, 8, and 10 and the node with value 6 is the first node of the loop. So we will output 6.

Now, I think from the above examples, the problem statement is clear.

Before moving to the approach section, try to think about how you can approach this problem. What is the first thing that comes to your mind?

The very first thing that comes to mind is loop detection. Correct, but we can also use hashing to solve this problem.

- The hashing solution will require O(n) space for the creation of the hash table, so we are first going to look at hashing approach, and then jump to the efficient loop detection approach.

Let us have a glance at the approach to get a clear look.

### Approach and Algorithm (Hashing)

In this approach, we are going to use hashing to solve the problem. Well, how can hashing help us?

- If we notice carefully, the first node of the loop is the first element that will appear twice while traversing the linked list with a loop.

1) We will first create a set, which will store the addresses of the nodes.

2) Now, we will traverse the given linked list. For every node, we will check if that node is present in the set or not.

- If it is not present, then we will simply insert it into the set.
- If the node is present in the set, it means that the current node is the first node of the loop. As the first node of the loop will be the first repeating node while traversing the list. So, if the node is present in the set, we will simply return that node.

This approach will work fine, but it requires extra O(n) space. So, now the main question is can we optimize this space?

- The answer is yes, and we will see how we can optimize this space in the next approach.

Our next approach uses Floydâ€™s Cycle Detection algorithm.

### Approach and Algorithm (Floydâ€™s Cycle Detection)

Our approach will be simple:

1) Firstly, we have to detect the loop in the given linked list.

- For detecting a loop in any linked list, we know the most efficient algorithm is the
**Floyd Cycle detection Algorithm**.

2) In Floyd's cycle detection algorithm, we initialize 2 pointers, **slow** and **fast**.

- Both initially point to the head of the list.
- The
**slow**pointer jumps one place and the**fast**pointer jumps 2 places. - The node at which the
**slow**and**fast**pointer meet is a**loop node**.

3) Now, after finding the loop node:

- We will make 2 pointers
**ptr1**and**ptr2**, which will point to that**loop node**. - We will also initialize a variable to find the length of the loop. Now, how will we find the length of this loop?
**ptr2**will be fixed, and we will increment**ptr1**till it meets**ptr2**. As both are at the same position currently, when**ptr1**will meet**ptr2**, the whole loop would've been traversed, and we will get the length**k**.

4) Now, as we have the length of the loop, we will make **ptr1** and **ptr2** point to the **head** again.

5) Now, we will shift **ptr2** by **k** places.

6) After shifting, we will move both **ptr1** and **ptr2** simultaneously (taking 1 jump). The node at which **ptr1** and **ptr2** will meet will be the first node of the loop.

7) After finding the first node of the loop, we will return it.

#### Dry Run

### Approach and Algorithm (More Optimized Approach)

In the previous method, after finding the loop node, we were also running a for loop to find the length of the loop in the linked list. Can we find the first node of loop without finding the length of loop?

- The answer is Yes, and in this approach, we will see how we can do it.

This method will be very much similar to the previous one, but here we will try to avoid finding the length of loop.

1) Similar to the previous method, we will find the loop node using **Floyd Cycle detection Algorithm**.

2) After finding the **loop node**, we will initialize the **slow** pointer to the **head** of the linked list and the **fast** pointer will remain at its position.

3) Now we will start moving the **fast** and **slow** pointer one node at a time until they meet each other.

4) The node at which **slow** and **fast** meets will be the starting point or say the **first node of the loop**.

Now, letâ€™s see the dry run for this approach.

#### Dry Run

### Code Implementation

#includeusing namespace std; /* Structure of a linked list node */ struct Node { int key; struct Node* next; }; /* Using this we are creating a new list node */ Node* newNode(int key) { Node* temp = new Node; temp->key = key; temp->next = NULL; return temp; } /* Using this function we will be printing the list */ void printList(Node* head) { while (head != NULL) { cout << head->key << " "; head = head->next; } cout << endl; } /* Using this function we will find and return the first node of loop in the linked list */ Node* firstnode(Node* head) { if (head == NULL || head->next == NULL) return NULL; Node *slow = head, *fast = head; slow = slow->next; fast = fast->next->next; while (fast && fast->next) { if (slow == fast) break; slow = slow->next; fast = fast->next->next; } if (slow != fast) return NULL; slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } int main() { Node* head = newNode(1); head->next = newNode(0); head->next->next = newNode(3); head->next->next->next = newNode(0); head->next->next->next->next = newNode(1); head->next->next->next->next->next = head->next; Node* res = firstnode(head); if (res == NULL) cout << "Loop does not exist"; else cout << "Loop starting node is " << res->key; return 0; }

import java.util.*; public class PrepBytes{ /* Structure of a linked list node */ static class Node { int key; Node next; }; /* Using this we are creating a new list node */ static Node newNode(int key) { Node temp = new Node(); temp.key = key; temp.next = null; return temp; } /* Using this function we will be printing the list */ static void printList(Node head) { while (head != null){ System.out.print(head.key + " "); head = head.next; } System.out.println(); } /* Using this function we will find and return the first node of loop in the linked list */ static Node firstnode(Node head) { if (head == null || head.next == null) return null; Node slow = head, fast = head; slow = slow.next; fast = fast.next.next; while (fast != null && fast.next != null){ if (slow == fast) break; slow = slow.next; fast = fast.next.next; } if (slow != fast) return null; slow = head; while (slow != fast){ slow = slow.next; fast = fast.next; } return slow; } public static void main(String[] args) { Node head = newNode(1); head.next = newNode(0); head.next.next = newNode(3); head.next.next.next = newNode(0); head.next.next.next.next = newNode(1); head.next.next.next.next.next = head.next; Node res = firstnode(head); if (res == null) System.out.print("Loop does not exist"); else System.out.print("Loop starting node is " + res.key); } }

#include#include #include struct Node { int key; struct Node* next; }; /* Using this we are creating a new list node */ struct Node* newNode(int x) { struct Node* node = malloc(sizeof(struct Node*)); node->key = x; node->next = NULL; return node; } /* Using this function we will be printing the list */ void printList(struct Node* head) { while (head != NULL) { printf("%d ",head->key); head = head->next; } printf("\n"); } /* Using this function we will find and return the first node of loop in the linked list */ struct Node* firstnode(struct Node* head) { if (head == NULL || head->next == NULL) return NULL; struct Node *slow = head; struct Node *fast = head; slow = slow->next; fast = fast->next->next; while (fast && fast->next) { if (slow == fast) break; slow = slow->next; fast = fast->next->next; } if (slow != fast) return NULL; slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; } int main() { struct Node* head = newNode(1); head->next = newNode(0); head->next->next = newNode(3); head->next->next->next = newNode(0); head->next->next->next->next = newNode(1); head->next->next->next->next->next = head->next; struct Node* res = firstnode(head); if (res == NULL) printf("Loop does not exist"); else printf("Loop starting node is %d",res->key); return 0; }

class Node: def __init__(self, key): self.key = key self.next = None def newNode(key): temp = Node(key) return temp def printList(head): while (head != None): print(head.key, end = ' ') head = head.next print() def firstNode(head): if (head == None or head.next == None): return None slow = head fast = head slow = slow.next fast = fast.next.next while (fast and fast.next): if (slow == fast): break slow = slow.next fast = fast.next.next if (slow != fast): return None slow = head while (slow != fast): slow = slow.next fast = fast.next return slow if __name__=='__main__': head = newNode(1) head.next = newNode(0) head.next.next = newNode(3) head.next.next.next = newNode(0) head.next.next.next.next = newNode(1) head.next.next.next.next.next = head.next res = firstNode(head) if (res == None): print("Loop does not exist") else: print("Loop starting node is " + str(res.key))

#### Output

Loop starting node is 0

**Time Complexity:** O(n), as no nested traversal is needed.

[forminator_quiz id="5230"]

So, in this article, we have tried to explain the most efficient approach to find the first node of a loop in a linked list. Multiple concepts have been used here, so it makes this question an important one for coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.