Find the N^th Node from the end without using extra memory - Linked List

Given a singly-linked list, implement the method that returns Nth node from the end of the list without using extra memory (constant space complexity).

Examples:
1->2->3->4->5->6, n=2 ==> 5

Need a hand? Try out these hints, one at a time.

Quick hint to get things rolling

The key here is to avoid using extra memory to store the positions of the nodes. This can be done by traversing the List twice, one for finding the length and the other to return the position.

Final hint! You should be able to code the problem on viewing this.

We can get the position of the Nth Node from the end with the formula: 'length-n+1'.

1. First find the length of the List. Traverse the List one more time to the Nth position and return the Node.

2. Since we didn't use extra memory, the runtime is O(n) and space complexity is O(1)

public ListNode findNthNodeFromEnd(ListNode head, int n) {
               




    
}

This Coding Interview Question is available with an answer in the following programming languages :

Java

Python

Find the Nth Node from the end without using extra memory - Linked List

Quick hint to get things rolling

Final hint! You should be able to code the problem on viewing this.

The interview prep tool you'll fall in love with!

This Coding Interview Question is available with an answer in the following programming languages :

Find the N^th Node from the end without using extra memory - Linked List