Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Put a fast pointer k nodes ahead of a slow pointer; then move both until fast reaches the last node.
  2. 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