# Find modular node in a linked list

### Introduction

The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.

### Problem Statement

In this problem, we have been given a linked list and a positive integer k. Our task is to find the last node whose n%k==0, where n denotes the position of this last node in the linked list.

### Problem Statement Understanding

Let’s try to understand the problem with the help of examples by referring online programming courses.

Suppose we are given a linked list A → B → C → D → E → F and k = 3.

• According to the problem statement, we have to find the last node of the linked list whose n%k==0, where this n denotes the node's position in the linked list.
• For the above given linked list, we can see that only for n=3 and n=6 our n%k==0. But as 6>3:
• So we will have to return the 6th node of the linked list as our output, as it is the last node of the linked list for which n%k==0.

Output: F

If the linked list is A → B → C → D → E → F → G → H → I and k = 4.

• For the above given linked list, we can see that only for n=4 and n=8 our n%k==0. But as 8>4:
• So we will have to return the 8th node of the linked list as our output, as it is the last node of the linked list for which n%k==0.

Output: H

Note: Here in this problem, we are considering 1 based indexing.

##### Some more examples

Input : Output : 6

Input : Output : 9

Now I think from the above examples the problem is clear, and now we have to think about how we can approach it.

### Approach

Our approach will be simple:

• We will traverse the linked list and whenever for any node i%k==0 (i denotes the position of the current node in the linked list) we will update our modular node to be equal to the current node.
• Finally, we will have our modular node at the end of the loop, and now we can return it.

The algorithm for the approach is explained below.

### Algorithm

• We will take a pointer modNode and initialize it with NULL. This pointer will keep track of the last node whose i%k==0.
• Now we will traverse the list and for every i%k==0, we will update our modNode to be equal to the current node.
• Finally, at the end when our list traversal is over, we will return modNode as our output.

### Dry Run  ### Code Implementation

```#include

struct Node {
int data;
Node* next;
};

Node* newNode(int data)
{
Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}

{
if (k <= 0 || head == NULL)
return NULL;

int i = 1;
Node* modNode = NULL;
for (Node* temp = head; temp != NULL; temp = temp->next) {
if (i % k == 0)
modNode = temp;

i++;
}
return modNode;
}

int main()
{
int k = 2;
printf("\nModular node is ");