Follow

Follow

# 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.

Nhut Nguyen
Â·Nov 3, 2022Â·

### 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 = [1], n = 1
Output: []

#### Example 3

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

#### 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"

Support Nhut Nguyen by becoming a sponsor. Any amount is appreciated!