Practice › Linked List
Remove Nth Node From End
Medium · Linked List · Asked at Amazon, Microsoft, Google, Adobe
Remove the k-th node from the end of the list and print the remaining values (print -1 if the list becomes empty).
Input
First line: n. Second line: n values. Third line: k.
Output
The remaining list, or -1.
Constraints
- 1 ≤ k ≤ n ≤ 10^5
One pass: move a fast pointer k steps ahead, then move both until fast reaches the end.
Example 1
Input
5 1 2 3 4 5 2
Output
1 2 3 5
Example 2
Input
1 1 1
Output
-1
Hints
- Put a fast pointer k nodes ahead of a slow pointer; then move both until fast reaches the last node.
- Start both at a dummy node placed before head — that makes deleting the head itself work with the same code.
Approach
Add a dummy node before head. Move fast k steps from the dummy, then move fast and slow together until fast.next is null. Slow now sits just before the node to delete: set slow.next = slow.next.next. Because of the dummy, removing the head (k = n) needs no special case. If the list becomes empty, print -1.
Complexity: O(n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
struct Node {
long long val;
Node *next;
Node(long long v) : val(v), next(nullptr) {}
};
int main() {
int n, k;
cin >> n;
Node dummy(0), *tail = &dummy;
for (int i = 0; i < n; i++) {
long long v;
cin >> v;
tail = tail->next = new Node(v);
}
cin >> k;
Node *fast = &dummy, *slow = &dummy;
for (int i = 0; i < k; i++) fast = fast->next;
while (fast->next) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
if (!dummy.next) cout << -1 << "\n";
for (Node *p = dummy.next; p; p = p->next) cout << p->val << (p->next ? " " : "\n");
return 0;
}Python solution
import sys
class Node:
def __init__(self, val, nxt=None):
self.val, self.next = val, nxt
data = sys.stdin.read().split()
n = int(data[0])
k = int(data[n + 1])
dummy = Node(None)
for v in reversed(data[1 : n + 1]):
dummy.next = Node(v, dummy.next)
fast = slow = dummy
for _ in range(k):
fast = fast.next
while fast.next:
fast, slow = fast.next, slow.next
slow.next = slow.next.next
out, p = [], dummy.next
while p:
out.append(p.val)
p = p.next
print(" ".join(out) if out else -1)Java solution
import java.util.*;
public class Main {
static class Node {
long val;
Node next;
Node(long v) { val = v; }
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Node dummy = new Node(0), tail = dummy;
for (int i = 0; i < n; i++) tail = tail.next = new Node(sc.nextLong());
int k = sc.nextInt();
Node fast = dummy, slow = dummy;
for (int i = 0; i < k; i++) fast = fast.next;
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
if (dummy.next == null) {
System.out.println(-1);
return;
}
StringBuilder sb = new StringBuilder();
for (Node p = dummy.next; p != null; p = p.next) sb.append(p.val).append(p.next != null ? " " : "");
System.out.println(sb);
}
}Solve Remove Nth Node From End online · All practice problems