1. Introduction

Linked lists are versatile data structures that allow for easy insertion and deletion of nodes. Occasionally, we might need to delete nodes at regular intervals, like every k-th node. In this blog post, we will implement a method to remove every k-th node from a linked list in Java.

2. Program Steps

1. Define a Node class to represent each element of the linked list.

2. Implement a LinkedList class to manage the list operations.

3. Within the LinkedList class, add a method named removeEveryKthNode(int k):

– Traverse the list, and for every k-th node, remove it.

– Ensure corner cases (like k = 1) are handled appropriately.

4. Test the functionality with a driver method.

3. Code Program

class Node {
    int data;
    Node next;

    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    // Add a new node at the end
    public void append(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

    // Remove every k-th node
    public void removeEveryKthNode(int k) {
        if (k <= 0 || head == null) return;

        if (k == 1) {
            head = null;  // Entire list is removed
            return;
        }

        int count = 1;
        Node temp = head;
        Node prev = null;
        while (temp != null) {
            if (count % k == 0) {
                prev.next = temp.next;
            } else {
                prev = temp;
            }
            temp = temp.next;
            count++;
        }
    }

    // Utility function to print the list
    public void printList() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " -> ");
            temp = temp.next;
        }
        System.out.println("NULL");
    }
}

public class LinkedListDemo {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        for (int i = 1; i <= 10; i++) {
            list.append(i);
        }

        System.out.println("Original List:");
        list.printList();

        list.removeEveryKthNode(3);

        System.out.println("\nList after removing every 3rd node:");
        list.printList();
    }
}

Output:

Original List:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> 10 -> NULL

List after removing every 3rd node:
1 -> 2 -> 4 -> 5 -> 7 -> 8 -> 10 -> NULL

4. Step By Step Explanation

1. The Node class represents an individual element of the linked list. Each node contains data and a reference to the next node.

2. The LinkedList class manages the linked list operations. The append method is used to add elements to the end of the list.

3. The removeEveryKthNode method is the crux of this implementation:

– If k is less than or equal to 0, or if the head is null, we simply return.

– If k is 1, it means every node is to be removed, so the entire list is deleted.

– Otherwise, we traverse the list and maintain a count. Whenever the count is a multiple of k, the node at that position is removed.

4. In the LinkedListDemo class, we demonstrate the functionality by creating a linked list with numbers 1 to 10 and then removing every 3rd node.