Deleting Every Kth Node in a Circular Linked List in Java

By Lokeswara Reddy Ajjuguttu

In this Java post, we will be learning how to delete every kth node in a Circular Linked List and find the last remaining node value.

In general, a Single Linked List is a Data Structure in which each node has two fields. One is data field and the other is pointer field. Data field holds the information part and the pointer field holds the address of the next node (Here in Java we will not be using pointers and addresses they are implemented  using references). The first node is called as the head and the last node is called as tail. The last node's pointer  field is set to null in case of a Single Linked List.

Similarly, a Circular Linked List is a type of Single Linked List in which the last node  points to the head(first node) of that Linked List i.e... last node's pointer field is filled with the address of the first node.

Here, we will be given a Circular Linked List of "N" nodes(for simplicity node values are filled with numbers from 1 to N) and an Integer "K". Now, we required to delete the node numbered K and again start counting from the next node and again delete the node numbered K. Continue this process till a single node is remaining in the List. Finally print the value present at that node.

Approach:

1. Create a Java class (named LinkedListNode) which has two fields named data field and link field.

class LinkedListNode {
    int data;
//    data field contains the value at that node
    LinkedListNode link;
//    link is like a pointer which holds the address of the next node.

2. Initialize a constructor which takes values of either data field or both fields to initialize the vlues when passed as arguments.

//  LinkedListNode(int) constructor to initialize values when only data part is passed.

LinkedListNode(int data) {
this.data = data;
this.link = null;
}

// LinkedListNode(int, LinkedListNode) constructor to initialize values when both the data part and next part are passed.

LinkedListNode(int data, LinkedListNode link) {
this.data = data;
this.link = link;
}

3. Now take the input value of "N" and "K".

4. Now call a method which creates a Circular Linked List containing data values from 1 to N and return the head  of that List.

5. Take two pointers(here references of the class LinkedListNode) named temp and bef. Where temp points to the node that  is to be deleted and bef points to the node before to the node pointed by temp. Initially temp is initialized to point to head and bef points to null.

6. Now take a variable count which is initialized to 1.

7. Now iterate a loop till the value of N is reached to 1.

8. We keep updating the value of count. If we get count%K==0 then we  change the link part of bef pointer o point to (temp.link). So, that the link to the temp node is vanished and hence the temp node is deleted. If it is a head node then we should also update the value of the head.

9. If count%K!=0 then we simply update the bef and temp values.

10. This process is continued till we end up having a sinle node present i.e... till n=1.

11. Finally  the remaining node is pointed by the bef pointer (or) the head pointer. Hence we can simply print the value present at that node .

Input:

Enter the value fo N

5

Enter the value of K

2

Output:

The last remaining node is 3.

Explanation for the above input value:

Here N=5 and K=2.

So the Circular Linked List is

1 -> 2 -> 3 -> 4 -> 5.

After deleting first 2nd node the List becomes:

1 -> 3 -> 4 -> 5.

After deleting for the second time the List becomes:

1 -> 3 -> 5.

After deleting for the second time the List becomes:

3 -> 5.

After deleting for the second time the List becomes:

3.

So finally the last remaining node required is 3.