Last Updated: 2 Dec, 2020
Find Node
Moderate
Asked in companies
You are given a linked list with a cycle. You need to find and return the Nth node from where the cycle starts in the input Linked List (moving towards the head of the linked list).
The cycle is created by connecting the last element of Linked List (i.e., tail) to some other node given in input.
Return null if no such part exists.
The counting of nodes starts from 1.
For Example:
head = [5 , 4 , 0 , -1]
pos = 2
N = 1
You have to find the node where the cycle begins and return the Nth node from that point in the direction of the head.
Input format :
The first line contains a single integer ‘T’ denoting the number of test cases to be run. Then the test cases follow.
The first line of each test case contains elements of a linked list terminated by -1, (hence -1 will never be the value of any node in the linked list.
The second line of each test case contains an integer representing the position where the cycle begins.
The third line of each test case contains an integer N, denoting the position to find.
Output format :
For each test case print, an integer denoting the Nth node from the start of the loop.
Constraints :
1 <= T <= 50
1 <= X <= 10^4
-10^5 <= Node.val <= 10^5
1 <= N <= 10^5
Where ‘X’ is the number of nodes in the linked list.
Time Limit: 1 sec.
Approaches
We will detect the cycle and the node where the cycle begins. Then we will find the nth node using two pointers. One at the head and the other N- node away.
Algorithm:-
A. Use a helper function to determine the presence of cycle and entry node:-
- Initialize a pointer to the linked list ‘SLOW’ pointing to the head of the linked list, that moves forward 1 step each time, and a pointer ‘FAST’ that moves forward two steps each time
- If the ‘SLOW’ pointer and ‘FAST’ pointer point to the same node, then there is a cycle.
- Otherwise, if the fast pointer next is NULL, there is no cycle.
- If there is a cycle, find the entry node of the cycle. To find the loop’s starting, Keep the ‘SLOW’ pointer to the head and the ‘FAST’ pointer at the same place.
- Now keep increasing both ‘SLOW’ and ‘FAST’by one step till they meet.
B. Now in the given function:-
- To find the ‘N’th node, use two pointer nodes, one at the head and the other ‘N’ node away from the head.
- Move both pointers by one node till the second pointer reaches the meeting node.
- The first pointer will be our required nth node.