Remove Nth Node from End
In this page:
Problem
This problem asks you to remove the node that's n positions from the end of a linked list, in a single pass, without first counting the list's total length in a separate traversal.
Example: Problem
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* head = new Node{1, new Node{2, new Node{3, new Node{4, nullptr}}}};
cout << "remove the 2nd node from the end, in a single pass, n=2" << endl;
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node head = new Node(1); head.next = new Node(2);
System.out.println("remove the 2nd node from the end, in a single pass, n=2");
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
head = Node(1); head.next = Node(2)
print("remove the 2nd node from the end, in a single pass, n=2")#include <stdio.h>
int main() {
printf("remove the 2nd node from the end, in a single pass, n=2\n");
return 0;
}Login to try C/C++/Java code in the editor
Two Pointer Method
A two-pointer technique solves it elegantly: advance one pointer n steps ahead of the other first, then move both pointers forward together, so the gap between them stays exactly n nodes wide the whole time.
Example: Two Pointer Method
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* head = new Node{1, new Node{2, new Node{3, new Node{4, nullptr}}}};
Node* lead = head; Node* trail = head;
int n = 2;
for (int i = 0; i < n; i++) lead = lead->next;
cout << "lead advanced " << n << " steps ahead of trail; gap stays " << n << " nodes wide" << endl;
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node head = new Node(1); head.next = new Node(2); head.next.next = new Node(3);
Node lead = head, trail = head;
int n = 2;
for (int i = 0; i < n; i++) lead = lead.next;
System.out.println("lead advanced " + n + " steps ahead of trail; gap stays " + n + " nodes wide");
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
head = Node(1); head.next = Node(2); head.next.next = Node(3)
lead = trail = head
n = 2
for _ in range(n):
lead = lead.next
print("lead advanced", n, "steps ahead of trail; gap stays", n, "nodes wide")#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *n3 = malloc(sizeof(struct Node)); n3->data = 3; n3->next = NULL;
struct Node *n2 = malloc(sizeof(struct Node)); n2->data = 2; n2->next = n3;
struct Node *head = malloc(sizeof(struct Node)); head->data = 1; head->next = n2;
struct Node *lead = head;
int n = 2;
for (int i = 0; i < n; i++) lead = lead->next;
printf("lead advanced %d steps ahead; gap stays %d nodes wide\n", n, n);
return 0;
}Login to try C/C++/Java code in the editor
Remove Node
By the time the leading pointer reaches the end of the list, the trailing pointer is positioned exactly one node before the target, which is precisely where you need to be to unlink it by updating a next pointer.
Example: Remove Node
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node dummy{0, new Node{1, new Node{2, new Node{3, new Node{4, nullptr}}}}};
Node* lead = &dummy; Node* trail = &dummy;
int n = 2;
for (int i = 0; i < n + 1; i++) lead = lead->next;
while (lead) { lead = lead->next; trail = trail->next; }
trail->next = trail->next->next;
for (Node* c = dummy.next; c; c = c->next) cout << c->data << " ";
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node dummy = new Node(0);
dummy.next = new Node(1); dummy.next.next = new Node(2);
dummy.next.next.next = new Node(3); dummy.next.next.next.next = new Node(4);
Node lead = dummy, trail = dummy;
int n = 2;
for (int i = 0; i < n + 1; i++) lead = lead.next;
while (lead != null) { lead = lead.next; trail = trail.next; }
trail.next = trail.next.next;
for (Node c = dummy.next; c != null; c = c.next) System.out.print(c.data + " ");
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
dummy = Node(0)
dummy.next = Node(1); dummy.next.next = Node(2)
dummy.next.next.next = Node(3); dummy.next.next.next.next = Node(4)
lead = trail = dummy
n = 2
for _ in range(n + 1):
lead = lead.next
while lead:
lead = lead.next
trail = trail.next
trail.next = trail.next.next
c = dummy.next
while c:
print(c.data, end=" ")
c = c.next#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *n4 = malloc(sizeof(struct Node)); n4->data = 4; n4->next = NULL;
struct Node *n3 = malloc(sizeof(struct Node)); n3->data = 3; n3->next = n4;
struct Node *n2 = malloc(sizeof(struct Node)); n2->data = 2; n2->next = n3;
struct Node *n1 = malloc(sizeof(struct Node)); n1->data = 1; n1->next = n2;
struct Node dummy = {0, n1};
struct Node *lead = &dummy, *trail = &dummy;
int n = 2;
for (int i = 0; i < n + 1; i++) lead = lead->next;
while (lead) { lead = lead->next; trail = trail->next; }
trail->next = trail->next->next;
for (struct Node *c = dummy.next; c; c = c->next) printf("%d ", c->data);
return 0;
}Login to try C/C++/Java code in the editor
Dummy Node
Using a dummy node placed just before the real head sidesteps a tricky edge case: without it, removing the very first node of the list would need special-case logic, since there's no previous node to update otherwise.
Example: Dummy Node
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node* real = new Node{1, new Node{2, nullptr}};
Node dummy{0, real};
cout << "dummy.next points at the real head, so removing head needs no special case: " << dummy.next->data << endl;
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node real = new Node(1); real.next = new Node(2);
Node dummy = new Node(0); dummy.next = real;
System.out.println("dummy.next points at the real head, so removing head needs no special case: " + dummy.next.data);
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
real = Node(1); real.next = Node(2)
dummy = Node(0)
dummy.next = real
print("dummy.next points at the real head, no special case needed:", dummy.next.data)#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *real = malloc(sizeof(struct Node)); real->data = 1; real->next = NULL;
struct Node dummy = {0, real};
printf("dummy.next points at real head, no special case needed: %d\n", dummy.next->data);
return 0;
}Login to try C/C++/Java code in the editor
Complexity
This two-pointer approach removes the target node in a single O(n) pass using only O(1) extra space, compared to a two-pass solution that first counts the list's length and then walks to the removal point.
Example: Complexity
#include <iostream>
using namespace std;
struct Node { int data; Node* next; };
int main() {
Node dummy{0, new Node{1, new Node{2, new Node{3, nullptr}}}};
Node* lead = &dummy; Node* trail = &dummy;
int n = 1;
for (int i = 0; i < n + 1; i++) lead = lead->next;
while (lead) { lead = lead->next; trail = trail->next; }
trail->next = trail->next->next;
cout << "removed in a single O(n) pass, O(1) extra space" << endl;
return 0;
}class Node { int data; Node next; Node(int d) { data = d; } }
public class Main {
public static void main(String[] args) {
Node dummy = new Node(0);
dummy.next = new Node(1); dummy.next.next = new Node(2); dummy.next.next.next = new Node(3);
Node lead = dummy, trail = dummy;
int n = 1;
for (int i = 0; i < n + 1; i++) lead = lead.next;
while (lead != null) { lead = lead.next; trail = trail.next; }
trail.next = trail.next.next;
System.out.println("removed in a single O(n) pass, O(1) extra space");
}
}class Node:
def __init__(self, data):
self.data = data
self.next = None
dummy = Node(0)
dummy.next = Node(1); dummy.next.next = Node(2); dummy.next.next.next = Node(3)
lead = trail = dummy
n = 1
for _ in range(n + 1):
lead = lead.next
while lead:
lead = lead.next
trail = trail.next
trail.next = trail.next.next
print("removed in a single O(n) pass, O(1) extra space")#include <stdio.h>
#include <stdlib.h>
struct Node { int data; struct Node *next; };
int main() {
struct Node *n3 = malloc(sizeof(struct Node)); n3->data = 3; n3->next = NULL;
struct Node *n2 = malloc(sizeof(struct Node)); n2->data = 2; n2->next = n3;
struct Node *n1 = malloc(sizeof(struct Node)); n1->data = 1; n1->next = n2;
struct Node dummy = {0, n1};
struct Node *lead = &dummy, *trail = &dummy;
int n = 1;
for (int i = 0; i < n + 1; i++) lead = lead->next;
while (lead) { lead = lead->next; trail = trail->next; }
trail->next = trail->next->next;
printf("removed in a single O(n) pass, O(1) extra space\n");
return 0;
}Login to try C/C++/Java code in the editor
🔒
Chapter Quiz — Complete all 8 topics to unlock
0/8 topics done
Complete these topics first: