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;
}

Node* modularNode(Node* head, int k)
{
    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()
{
    Node* head = newNode(1);
    head->next = newNode(3);
    head->next->next = newNode(5);
    head->next->next->next = newNode(7);
    head->next->next->next->next = newNode(9);
    int k = 2;
    Node* answer = modularNode(head, k);
    printf("\nModular node is ");
    if (answer != NULL)
        printf("%d\n", answer->data);
    else
        printf("null\n");
    return 0;
}

Output

Modular node is 7

Time Complexity: O(n), as we are traversing the complete length of the list

So, in this article, you have learnt how to get the value of the modular node in the Linked List. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.

Previous post Insert a node into the middle of the linked list
Next post Java.util.LinkedList.get(), getFirst() and getLast() in Java

Leave a Reply

Your email address will not be published. Required fields are marked *