## Description

Given a linked list, remove the n-th node from the end of list and return its head.

Example:

Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.

Note: Given n will always be valid.

## Naive solution

First, we need to get the `length`

of the link list, the time complexity will be \(O(N)\), we can not avoid this step, so this is also the best time complexity.

Given the `length`

of link list, remove the `n-th`

node will be easy if we find the node at pos `length-n`

.

Note a `dummy node`

will make the code cleaner.

```
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* cur = head;
int len = 0;
while(cur) {
cur = cur->next;
len++;
}
len -= n;
cur = dummy;
while(len > 0) {
cur = cur->next;
len--;
}
cur->next = cur->next->next;
return dummy->next;
}
};
```

## Approach with two pointers

This is a clever approach, if we use two pivot pointers, their distance is `n+1`

. Then if we move the tail forward to the end of linklist, the `prev`

will be the pointer whose next can be deleted!

```
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode root(0);
root.next = head;
ListNode* prev = &root;
ListNode* tail = head;
while(n--) tail = tail->next;
while (tail){
tail = tail->next;
prev = prev->next;
}
prev->next = prev->next->next;
return root.next;
}
};
```