5

Find Node

Difficulty: MEDIUM
Avg. time to solve
25 min
Success Rate
70%

Problem Statement

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.
Sample Input 1 :
2
5 4 0 -1
2
1
9 8 1 2 5 14 -1
5
3
Sample Output 1 :
5
8
Explanation:
For test case one:- The cycle starts at 4. So the 1st node from 4 in the direction of the head is 5.
For test case two:- The cycle starts at 5. So the 3rd node from 5 in the direction of the head is 8.
Sample Input 2 :
2
1 2 3 4 5 6 7 8 -1
4
2
5 4 3 2 1 -1
3
4
Sample Output 2 :
2
null
Reset Code
Full screen
copy-code
Console