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

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
Explanation: The second node(n = 2) from the end is deleted from the linked list.

Example 2

Input: 1->2->3->4, n=4
Output: 2->3->4
Explanation: The fourth node(n = 4) from the end having value 1 is deleted from the linked list.

Example 3

Input: 4->9->1->2, n=1
Output: 4->9->1
Explanation: The first node(n = 1) from the end having value 2 is deleted from the linked list.