# Nhut Nguyen # C++ Solution to Coding Challenge 19. Remove Nth Node From End of List

## Using the two-pointer technique to remove a node in a linked list.

### Problem statement

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

#### Example 1 ``````Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]
``````

#### Example 2

``````Input: head = , n = 1
Output: []
``````

#### Example 3

``````Input: head = [1,2], n = 1
Output: 
``````

#### Constraints

• The number of nodes in the list is `sz`.

• `1 <= sz <= 30`.

• `0 <= Node.val <= 100`.

• `1 <= n <= sz`.

Follow up: Could you do this in one pass?

### Solution 1: Store the nodes

#### Code

``````#include <iostream>
#include <vector>
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
using namespace std;
ListNode* removeNthFromEnd(ListNode* head, int n) {
vector<ListNode*> nodes;
while (node)
{
nodes.push_back(node);
node = node->next;
}
node = nodes[nodes.size() - n];
} else {
ListNode* pre = nodes[nodes.size() - n - 1];
pre->next = node->next;
}
}
cout << "[";
while (node) {
cout << node->val << ",";
node = node->next;
}
cout << "]\n";
}
int main() {
ListNode five(5);
ListNode four(4, &five);
ListNode three(3, &four);
ListNode two(2, &three);
ListNode one(1, &two);
}
``````
``````Output:
[1,2,3,5,]
[]
[4,]
``````

#### Complexity

• Runtime: `O(sz)`, where `sz` is the number of nodes in the list.

• Extra space: `O(sz)`.

### Solution 2: Two pointers

The distance between the removed node and the end (`nullptr`) of the list is always `n`.

You can apply the two-pointer technique as follows.

Let the slower runner start after the faster one `n` nodes. Then when the faster reaches the end of the list, the slower reaches the node to be removed.

#### Code

``````#include <iostream>
#include <vector>
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
using namespace std;
ListNode* removeNthFromEnd(ListNode* head, int n) {
for (int i = 0; i < n; i++) {
fast = fast->next;
}
if (fast == nullptr) {
}
while (fast->next)
{
slow = slow->next;
fast = fast->next;
}
slow->next = slow->next->next;
}
cout << "[";
while (node) {
cout << node->val << ",";
node = node->next;
}
cout << "]\n";
}
int main() {
ListNode five(5);
ListNode four(4, &five);
ListNode three(3, &four);
ListNode two(2, &three);
ListNode one(1, &two);
}
``````
``````Output:
[1,2,3,5,]
[]
[4,]
``````

#### Complexity

• Runtime: `O(sz)`, where `sz` is the number of nodes in the list.

• Extra space: `O(1)`.

### References

Get my FREE book "10 Classic Coding Challenges"