Problem

Submissions

Hints & solutions

Discuss

N-th Node From The End

Easy

0/40

Average time to solve is 10m

Contributed by

15 upvotes

Asked in companies

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )

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

Sample Input 1

2
1 -2 0 4 -1
2
9 9 -1
1

Sample Output 1

0
9

Explanation for Sample Input 1

In the 1st test case, the 2nd node from the end is 0.
In the 2nd  test case, the 1st node from the end is 9.

Sample Input 2

2
1 1 1 2 5 -1
4
6 -3 -1
2

Sample Output 2

1
6

Hint 1

Hint 2

Find the relation between the position of node from the start and end of the linked list.

Approaches (2)

Approach 1

Approach 2

Brute-Force

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.

Time Complexity

O(L), Where ‘L’ is the number of nodes in the linked list.

In the worst case, we will traverse the list twice, and traversing the list takes O(L) time, thus the final time complexity is O(2 * L) = O(L).

Space Complexity

O(1)

Constant additional space is required. Thus, the final space complexity is O(1).

(100% EXP penalty)

N-th Node From The End

Console