Find Node

Moderate
0/80
Average time to solve is 25m
14 upvotes
Asked in companies
IntuitNetlinkAirtel

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.

Detailed explanation ( Input/output format, Notes, Images )
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
Hint

Try to solve this using two pointers, moving at different speeds.

Approaches (1)
Using Slow and Fast Pointer

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:-   

  1. 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
  2. If the ‘SLOW’ pointer and ‘FAST’ pointer point to the same node, then there is a cycle.
  3. Otherwise, if the fast pointer next is NULL, there is no cycle.
  4. 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.
  5. Now keep increasing both ‘SLOW’ and ‘FAST’by one step till they meet.

B. Now in the given function:-

  1. To find the ‘N’th node, use two pointer nodes, one at the head and the other ‘N’ node away from the head.
  2. Move both pointers by one node till the second pointer reaches the meeting node.
  3. The first pointer will be our required nth node.
Time Complexity

O(N), where N is the number of nodes in the Linked List.

 

We are traversing the whole linked list Hence the overall complexity will be O(N)

Space Complexity

O(1)

 

Constant extra space is used.

Code Solution
(100% EXP penalty)
Find Node
Full screen
Console