# LeetCode Remove Nth Node From End of List: Two Pointers in One Pass

## Overview

LeetCode Remove Nth Node From End of List: keep 2 pointers p1 p2 with their distance to be n, p1 points to the desired node once p2 points to the end of list.

## LeetCode Remove Nth Node From End of List

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

For 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.
Try to do this in one pass.

## Solution Analysis: Two Pointers in One Pass

Keep three pointers, `previous`, `deleted`, `the_end`, at first, all of them point to the head of the list, and advance the_end pointer by n positions, and then and advance both `deleted` and `the_end` pointers by one position, then keep moving all of the three pointers one by one position until `the_end` pointer reaches the end of the list, now only by one pass, `deleted` points to exactly the node  when want to delete, and `previous` points to the node just before it. One can easily do deletion by using `previous` and `deleted`. The following code is accepted by the LeetCode OJ to pass this Remove Nth Node From End of List problem:

```class Solution {
public:
ListNode *removeNthFromEnd(ListNode *head, int n) {
if (NULL == head || n < 1)

ListNode s(0);
ListNode *p0 = &s;

for (int i = n - 1; i > 0 && p2; --i)
p2 = p2->next;

while (p2->next) {
p0 = p0->next;
p1 = p1->next;
p2 = p2->next;
}

p0->next = p1->next;
p1->next = NULL;
delete p1;
return s.next;
}

};
```

## Summary

LeetCode Remove Nth Node From End of List: keep 2 pointers p1 p2 with their distance to be n, p1 points to the desired node once p2 points to the end of list.

Written on April 21, 2013