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:

Examples:

`1->2->3->4->5->6, n=2 ==> 5`

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

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.
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) { }

**C**

**Java**

**Python**