You are given a linked list, write a program to remove the nth node from the end of the list and return the head.

Problem Note:

  • It is guaranteed that n ≤ length of linked list
  • Try to do this in one iteration.

Example 1

Input: 2->6->1->9, n=2
Output: 2->6->9

Example 2

Input: 1->2->3->4, n=4
Output: 2->3->4

Example 3

Input: 4->9->1->2, n=1
Output: 4->9->1