Nth node from end of linked list (DSA)

 

Problem Statement:(👈click here for GFG)

Given a linked list consisting of L nodes and given a number N. The task is to find the Nth node from the end of the linked list.

Example 1:

Input:
N = 2
LinkedList: 1->2->3->4->5->6->7->8->9
Output: 8
Explanation: In the first example, there
are 9 nodes in linked list and we need
to find 2nd node from end. 2nd node
from end is 8.  

Example 2:

Input:
N = 5
LinkedList: 10->5->100->5
Output: -1
Explanation: In the second example, there
are 4 nodes in the linked list and we
need to find 5th from the end. Since 'n'
is more than the number of nodes in the
linked list, the output is -1.

Your Task:
The task is to complete the function getNthFromLast() which takes two arguments: reference to head and N and you need to return Nth from the end or -1 in case node doesn't exist.

Note:
Try to solve in a single traversal.

Expected Time Complexity: O(N).
Expected Auxiliary Space: O(1).

Constraints:
1 <= L <= 106
1 <= N <= 106

Solution:

class Solution {
    //Function to find the data of nth node from the end of a linked list
    getNthFromLast(head, n)
    {
        let len = 0;
        let curr = head;
        
        //counting the length of the linked list
        while(curr != null) {
            len++;
            curr = curr.next;
        }
        
        //if n is greater than length of linked list, return -1
        if(n > len) {
            return -1;
        }
        
        //finding the position of node to be returned from beginning
        let position = len - n + 1;
        curr = head;
        let count = 1;
        
        //iterating till the position to get the node
        while(count < position) {
            curr = curr.next;
            count++;
        }
        
        //returning the data of the node
        return curr.data;
    }
}