Challenge: Remove Every k-th Coach

Lab Java Intermediate 20 points

Build a linked list of n numbers. Remove every k-th node (the k-th, 2k-th, 3k-th … counted in the original list) by relinking, then print what is left, or empty.

Input

Line 1: n k (k ≥ 1). Line 2: n whole numbers.

Output

The remaining numbers, or empty.

Example

Input

7 3
1 2 3 4 5 6 7

Output

1 2 4 5 7

Sample input available Sample output available

Editor

Java

Hints

A dummy node in front of the head means you never need a special case for removing the first node.

Count positions as you go. To remove, set prev.next = prev.next.next and don't move prev.

Solution explanation

One pass, O(n). The dummy node trick is used in many linked list problems.

Show solution

import java.util.Scanner;

class Node {
    int value;
    Node next;
    Node(int value) { this.value = value; }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), k = sc.nextInt();
        Node dummy = new Node(0);            // a fake node before the head makes removing the head easy
        Node tail = dummy;
        for (int i = 0; i < n; i++) {
            tail.next = new Node(sc.nextInt());
            tail = tail.next;
        }
        Node prev = dummy;
        int position = 1;
        while (prev.next != null) {
            if (position % k == 0) prev.next = prev.next.next;   // skip it
            else prev = prev.next;
            position++;
        }
        if (dummy.next == null) {
            System.out.println("empty");
            return;
        }
        StringBuilder sb = new StringBuilder();
        for (Node c = dummy.next; c != null; c = c.next) {
            if (c != dummy.next) sb.append(' ');
            sb.append(c.value);
        }
        System.out.println(sb);
    }
}

Output

Answer