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<stdio.h>
#include<stdlib.h>

struct Node {
    int data;
    struct Node* next;
};
 
/* Function to create a new node with given data */
struct Node* newNode(int data)
{
    struct Node* new_node = malloc(sizeof(struct Node*));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}
 
/* Function to find modular node in the linked list */
struct Node* modularNode(struct Node* head, int k)
{
    // Corner cases
    if (k <= 0 || head == NULL)
        return NULL;  
 
    // Traverse the given list
    int i = 1;
    struct Node* modularNode = NULL;
    for (struct Node* temp = head; temp != NULL; temp = temp->next) {
        if (i % k == 0)
            modularNode = temp;
         
        i++;
    }
    return modularNode;
}
 
/* Driver program to test above function */
int main(void)
{
    struct Node* head = newNode(1);
    head->next = newNode(2);
    head->next->next = newNode(3);
    head->next->next->next = newNode(4);
    head->next->next->next->next = newNode(5);
    int k = 2;
    struct Node* answer = modularNode(head, k);
    printf("\nModular node is ");
    if (answer != NULL)
        printf("%d\n", answer->data);
    else
        printf("null\n");
    return 0;
}
#include <bits stdc++.h="">

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;
}
class Modular
{
    static class Node
    {
        int data;
        Node next;
        Node(int data){
            this.data = data;
        }
    }
    static Node modularNode(Node head, int k)
    {
        if (k <= 0 || head == null)
            return null;
    
        int i = 1;
        Node modularNode = null;
        for (Node temp = head; temp != null; temp = temp.next) {
            if (i % k == 0)
                modularNode = temp;
            
            i++;
        }
        return modularNode;
    }
    public static void main(String[] args)
    {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);
        int k = 2;
        Node answer = modularNode(head, k);
        System.out.print("Modular node is ");
        if (answer != null)
            System.out.println(answer.data);
        else
            System.out.println("null");
    }
}
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def newNode(data):
    new_node = Node(data)
    new_node.data = data
    new_node.next = None
    return new_node

def modularNode(head, k):
    
    if (k <= 0 or head == None):
        return None

    i = 1
    modularNode = None
    temp = head
    while (temp != None):
        if (i % k == 0):
            modularNode = temp

        i = i + 1
        temp = temp.next
    return modularNode

if __name__ == '__main__':
    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)
    k = 2
    answer = modularNode(head, k)
    print("Modular node is", end = ' ')
    if (answer != None):
        print(answer.data, end = ' ')
    else:
        print("None")

Output

Modular node is 7

Time Complexity: O(n), as we are traversing the complete length of the list
[forminator_quiz id=”4496″]

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.

Leave a Reply

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