Find the first node of loop in linked list
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.
Example 1:
Input: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.
Solution:
//{ Driver Code Starts
//Initial Template for C++
#include <bits/stdc++.h>
using namespace std;
struct Node
{
int data;
Node* next;
Node(int val)
{
data = val;
next = NULL;
}
};
void loopHere(Node* head, Node* tail, int position)
{
if(position==0) return;
Node* walk = head;
for(int i=1; i<position; i++)
walk = walk->next;
tail->next = walk;
}
// } Driver Code Ends
//User function Template for C++
/*struct Node
{
int data;
struct Node *next;
Node(int x) {
data = x;
next = NULL;
}
*/
class Solution
{
public:
int findFirstNode(Node* head)
{
Node *slow =head;
Node *fast = head;
int flag=0;
int ans=-1;
while(fast && slow){
slow = slow->next;
fast = fast->next->next;
if(fast==slow){
flag =1;
break;
}
}
if(flag==0) return -1;
Node *temp = head;
int n=1;
while(n>0){
if(temp==slow){
n=0;
return temp->data;
}
slow = slow->next;
temp = temp->next;
}
return ans;
}
};
//{ Driver Code Starts.
int main()
{
int t;
cin>>t;
while(t--)
{
int n, num;
cin>>n;
Node *head, *tail;
cin>> num;
head = tail = new Node(num);
for(int i=0 ; i<n-1 ; i++)
{
cin>> num;
tail->next = new Node(num);
tail = tail->next;
}
int pos;
cin>> pos;
loopHere(head,tail,pos);
Solution ob;
int ans = ob.findFirstNode(head);
cout<<ans<<"\n";
}
return 0;
}
// } Driver Code Ends