Given a singly Linked List L consisting of N nodes and an integer K, the task is to modify the value of each node of the given Linked List to its nearest multiple of K, not exceeding the value of the node.
Examples:
Input: LL: 1 -> 2 -> 3 -> 5, K = 2
Output: 0 -> 2 -> 2 -> 4
Explanation:
The resultant LL has values having less than the original LL value and is a multiple of K(= 2).Input: LL:13 -> 14 -> 26 -> 29 -> 40, K = 13
Output: 13 -> 13 -> 26 -> 26 -> 39
Approach: The given problem can be solved by traversing the given Linked List and for each node traversed, find the floor value, say val, of the node value divided by K and update the node values to val*K.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <iostream>using namespace std;// Structure of nodestruct node { int data; node* next;};// Function to replace the node N// by the nearest multiple of K node* EvalNearestMult(node* N, int K){ node* temp = N; int t; // Traverse the Linked List while (N != NULL) { // If data is less than K if (N->data < K) N->data = 0; else { // If the data of current // node is same as K if (N->data == K) N->data = K; // Otherwise change the value else { N->data = (N->data / K) * K; } } // Move to the next node N = N->next; } // Return the updated LL return temp;}// Function to print the nodes of// the Linked Listvoid printList(node* N){ // Traverse the LL while (N != NULL) { // Print the node's data cout << N->data << " "; N = N->next; }}// Driver Codeint main(){ // Given Linked List node* head = NULL; node* second = NULL; node* third = NULL; head = new node(); second = new node(); third = new node(); head->data = 3; head->next = second; second->data = 4; second->next = third; third->data = 8; third->next = NULL; node* t = EvalNearestMult(head, 3); printList(t); return 0;} |
Java
// Java program for the above approachimport java.io.*;class GFG { // Structure of node static class node { int data; node next; node(int d) { data = d; } } // Function to replace the node N // by the nearest multiple of K static node EvalNearestMult(node N, int K) { node temp = N; int t; // Traverse the Linked List while (N != null) { // If data is less than K if (N.data < K) N.data = 0; else { // If the data of current // node is same as K if (N.data == K) N.data = K; // Otherwise change the value else { N.data = (N.data / K) * K; } } // Move to the next node N = N.next; } // Return the updated LL return temp; } // Function to print the nodes of // the Linked List static void printList(node N) { // Traverse the LL while (N != null) { // Print the node's data System.out.print(N.data + " "); N = N.next; } } // Driver Code public static void main(String[] args) { // Given Linked List node head = new node(3); head.next = new node(5); head.next.next = new node(8); node t = EvalNearestMult(head, 3); printList(t); }}// This code is contributed by Dharanendra L V |
Python3
# Python program for the above approach# Structure of Nodeclass Node: def __init__(self, data): self.data = data; self.next = None; # Function to replace the Node N# by the nearest multiple of Kdef EvalNearestMult(N, K): temp = N; t; # Traverse the Linked List while (N != None): # If data is less than K if (N.data < K): N.data = 0; else: # If the data of current # Node is same as K if (N.data == K): N.data = K; # Otherwise change the value else: N.data = (N.data // K) * K; # Move to the next Node N = N.next; # Return the updated LL return temp;# Function to print Nodes of# the Linked Listdef printList(N): # Traverse the LL while (N != None): # Print Node's data print(N.data , end=" "); N = N.next; # Driver Codeif __name__ == '__main__': # Given Linked List head = Node(3); head.next = Node(5); head.next.next = Node(8); t = None; t = EvalNearestMult(head, 3); printList(t);# This code is contributed by gauravrajput1 |
C#
// C# program for the above approachusing System;public class GFG { // Structure of node public class node { public int data; public node next; public node(int d) { data = d; } } // Function to replace the node N // by the nearest multiple of K static node EvalNearestMult(node N, int K) { node temp = N; // Traverse the Linked List while (N != null) { // If data is less than K if (N.data < K) N.data = 0; else { // If the data of current // node is same as K if (N.data == K) N.data = K; // Otherwise change the value else { N.data = (N.data / K) * K; } } // Move to the next node N = N.next; } // Return the updated LL return temp; } // Function to print the nodes of // the Linked List static void printList(node N) { // Traverse the LL while (N != null) { // Print the node's data Console.Write(N.data + " "); N = N.next; } } // Driver Code public static void Main(String[] args) { // Given Linked List node head = new node(3); head.next = new node(5); head.next.next = new node(8); node t = EvalNearestMult(head, 3); printList(t); }}// This code is contributed by gauravrajput1 |
Javascript
<script>// Javascript program for the above approach// Structure of nodeclass node { constructor() { this.data = 0; this.next = null; }};// Function to replace the node N// by the nearest multiple of K function EvalNearestMult(N, K){ var temp = N; var t; // Traverse the Linked List while (N != null) { // If data is less than K if (N.data < K) N.data = 0; else { // If the data of current // node is same as K if (N.data == K) N.data = K; // Otherwise change the value else { N.data = parseInt(N.data / K) * K; } } // Move to the next node N = N.next; } // Return the updated LL return temp;}// Function to print the nodes of// the Linked Listfunction printList(N){ // Traverse the LL while (N != null) { // Print the node's data document.write( N.data + " "); N = N.next; }}// Driver Code// Given Linked Listvar head = null;var second = null;var third = null;head = new node();second = new node();third = new node();head.data = 3;head.next = second;second.data = 4;second.next = third;third.data = 8;third.next = null;var t = EvalNearestMult(head, 3);printList(t);// This code is contributed by rrrtnx.</script> |
Output:
3 3 6
Time Complexity: O(N)
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
