How to find a modular node in a linked list

Problem statement

Find the modular node in a linked list. If no modular node is found, then, return NULL.

Understanding the problem

To understand this problem, we need to first understand what a modular node is. Let's assume that we have a linked list and a number n. For this linked list, a modular node would be the last node of the linked list whose index is divisible by the number n. Let’s have a better understanding of this problem with the help of an example:

The linked list given above has seven nodes. If the value of the number n is given as 3, then the modular node would be the sixth node which has the value 6. The reason for that is if we start traversing the linked list with the first index being 1, then the last index, which is divisible by the number 3, is six. Therefore, the modular node would be the sixth node with the value 6. Now that we understand the problem, let's move to the solution.

Solution

The solution to this problem is simple. We need to traverse the linked list, divide the index by the number n, and if we find an index that is divisible by the number n, we store it. If there is an index greater than the current index we have, which is divisible by n, then that becomes our answer.

#include <iostream>
using namespace std;
struct Node{ 
  int data; 
  Node *next; 
};
class LinkedList{
    public:
    Node* head;
    LinkedList(){
      head = NULL; 
    }
    void insert(int val){
      Node* new_node = new Node;
      new_node->data = val;
      new_node->next = NULL;
      if (head == NULL)
        head = new_node;
      else{
        Node* temp = head;
        while(temp ->next !=NULL){
          temp = temp->next;
        }
        temp->next =new_node;
      }
    }
    void print(){
      Node* temp = head;
      while(temp != NULL){
        cout << temp->data << " ";
        temp = temp->next;
      }
      cout << endl;
    }
};
Node* Modular_node(Node* head,int n){
  Node* temp = head;
  Node* mod_node = NULL;
  int index=1;
  while(temp!=NULL){
    if (index%n == 0){
      mod_node = temp;
    }
    temp = temp-> next;
    index++;
  }
  return mod_node;
}
int main(){
  LinkedList list;
  list.insert(3);
  list.insert(1);
  list.insert(9);
  list.insert(6);
  list.insert(8);
  list.insert(2);
  int n=3;
  Node* mod_node = Modular_node(list.head,n);
  cout << "Linked list : ";
  list.print();
  if (mod_node!=NULL){
    cout << "The Modular Node of the linked list is : " << mod_node -> data;
  }
  else{
    cout<<"Modular Node for this linked list does not exist";
  }
  
}

Code explanation

Lines 1–39: These lines include how the linked list is made. For further information about the linked list and how it’s made, you can refer to the following link.
Line 40: The function Modular_node() is made.
Lines 41–43: The variable temp, mod_node, and index are initialized.
Lines 44–50: In this loop, we traverse the list and increase the index by 1 in every iteration, We check if the index is divisible by the number n, and if it is divisible, then we store the node as our answer.
Line 51: Initially, the value of mod_node is set to NULL, so if its value is not changed in the loop, we return it as NULL, and if it is changed, we return the modular node.
Lines 53–71: In our int main(), we initialize a list, insert different values then run our function on it. If NULL is returned, we print that there is no modular node, and if a node is returned, its value is printed.