# Remove Nth Node From End of List

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.

Could you do this in one pass?

Solution:

Find the depth of each node recursively, handle last and first node

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* next = NULL;
int tar;
int depth(ListNode* n){
if(!n){
return 0;
}
int d = depth(n->next) + 1;
if(d == tar - 1){
next = n;
}
else if(d == tar + 1){
n -> next = next;
}

return d;
}
ListNode* removeNthFromEnd(ListNode* head, int n) {
tar = n;
}

}
};


Two pointer 1. advance q by n 2. advance p,q until q->next reach end, then p is n+1 to last.

* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *q = p;
for(int i=0;i<n;i++) q = q->next;

if(q==NULL){