Given a singly-linked list, implement the method that returns Nth node from the end of the list. You are allowed to use extra memory for this implementation.

Examples:

Examples:

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

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

Since we are allowed to use extra space, we could use a Hashtable to find the nth node from the end - or the

`'length-n+1'`

th node.
1. Try using a `Hashtable`

to store the position and the actual `ListNode`

s as you iterate over them.

2. Use 'length-n+1' as the index.

3. Now that you have an index, look up the `Hashtable`

with the index as the key and return the node.

public ListNode findNthNodeFromEnd(ListNode head, int n) { }

**C**

**Java**

**Python**