« back

Find the first node of loop in linked list

Tags : linkedlist, 2pointers, geeksforgeeks, cpp, easy

Problem Statement - link #

Given a singly linked list of N nodes. Find the first node of the loop if the linked list has a loop. If a loop is present return the node data of the first node of the loop else return -1.

Your Task:

The task is to complete the function findFirstNode() which contains reference to the head as only argument. This function should return the value of the first node of the loop if the linked list contains a loop, else return -1.

Expected Time Complexity: O(n)
Expected Auxiliary Space: O(1)

Examples #

Example 1:

Output: 3
Explanation:
We can see that there exists a loop 
in the given linked list and the first
node of the loop is 3.

Example 2:

Output: -1
Explanation: No loop exists in the above
linked list.So the output is -1.

Constraints #

Solutions #


/*struct Node
{
    int data;
    struct Node *next;
    Node(int x) {
        data = x;
        next = NULL;
    }

*/
class Solution
{
    public:
     //Function to find first node if the linked list has a loop.
    int findFirstNode(Node* head)
    {
        // your code here
        int result = -1;
        Node* slowPtr = head, *fastPtr = head;
        while( fastPtr!=NULL && fastPtr->next!=NULL )
        {
            slowPtr = slowPtr->next;
            fastPtr = fastPtr->next->next;
            if( fastPtr==NULL || fastPtr->next==NULL )
                return result;            
            if( slowPtr==fastPtr ) 
            {
                if(slowPtr==head)
                {
                    while(slowPtr->next!=head) slowPtr = slowPtr->next;
                    result = slowPtr->next->data;
                    break;
                }
                slowPtr = head;
                while( slowPtr->next!=fastPtr->next )
                {
                    slowPtr = slowPtr->next;
                    fastPtr = fastPtr->next;
                }
                result = fastPtr->next->data;
                break;
            }
        }
        return result;
        
    }
};