Last Updated: 7 Dec, 2020
N-th Node From The End
Easy
Asked in companies
You are given a Singly Linked List of integers. You have to find the N-th node from end.
For Example
If the given list is (1 -> -2 -> 0 -> 4) and N=2:
Then the 2nd node from the end is 0.
Input Format
The first line of input contains a single integer T, representing the number of test cases or queries to be run.
The first line of each test case contains the elements of the linked list separated by a single space and terminated by -1. Hence, -1 would never be a list element.
The second line contains an integer ‘N’, the position of the node from the end which you have to find.
Output Format
For each test case, print the value of the N-th node from the end.
Print the output of each test case in a separate line.
Note
You do not need to print anything. Just implement the given function and return a pointer pointing to the node which is at the N-th position from the last of the linked list.
Constraints
1 <= T <= 10
1 <= L <= 10^4
-10^9 <= data <= 10^9
1<= N <= L
data != -1
Where 'L' is the number of nodes in the linked list, ‘data’ represents the value of the nodes of the list.
Time Limit: sec
Approaches
The basic idea is to find the total number of nodes in the list and then find N-th node from end by using the fact that -
Nth node from the end will be (L - N + 1)th node from the start.
(Note: ‘L’ denotes the length of the list.)
Algorithm
- Find the length of the list.
- Traverse the list up to (L - N + 1)th node.
- Return the (L - N + 1)th node.
The idea is to have 2 pointers: ‘ptr1’ and ‘ptr2’. Initially, both point to the head node.
Algorithm
- Move ‘ptr2’ to the Nth node from the head.
- Now move both pointers one by one until ‘ptr2’ reaches the end of the list.
- ‘ptr1’ will be the Nth node from the end.
Why does this work?
As discussed in ‘Approach 1’ Nth node from the end is (L - N + 1)th from the start.
We are moving ‘ptr2’ to the Nth node from the start, which is also (L - N + 1)th from the end. After this, we are moving both pointers until ‘ptr2’ reaches the end of the list. It means ‘ptr1’ will be at (L - N + 1)th from the start.