Question

3. Find the last node of a linked list of n elements whose index is a multiple of k (counted from 0). For example, if the list is

12 → 75 → 37 → 99 → 12 → 38 → 99 → 60 ↓

and k = 4, then it should return the second 12 (with index 4). The algorithm should take O(n) time and use O(1) extra space. Implement the following method in LinkedList.java. public T lastK(int k)

Answer 1

The method used to find the last element whose index value is divisible by given number is as follows.

If the list is empty, print that list is empty and stop. Otherwise take the first node of the list and store its value in a variable 'element'. Now traverse the list using while loop. If the index value of the current node is divisible by k then update the value of 'element' with the current node value. Repeat this step until the list is travered.

// import io library to take input from the user
import java.io.*; 
  
// Java program to implement a linked list
public class LinkedList { 

    Node head; // head of list 
        // create linked list object
        public static LinkedList list = new LinkedList();
    
        // Linked list Node. 
    // This inner class is made static 
    // so that main() can access it 
    static class Node { 

    // create variable and object data and nextdata node for pointing to nextdata node  
        int data; 
        Node nextdata; 
  
        // create Constructor 
        Node(int d) 
        { 
            data = d; 
            nextdata = null; 
        } 
    } 
  
    // Method to add a new node 
    public static LinkedList add(LinkedList list, int data) 
    { 
        // Create a new node with given data 
        Node newdata = new Node(data); 
        newdata.nextdata = null; 
  
        // If the Linked List is empty, 
        // then make the new node as head 
        if (list.head == null) { 
            list.head = newdata; 
        } 
        else { 
            // id list is non empty then traverse the list
            // and add the newdata at the end
            Node last = list.head; 
            while (last.nextdata != null) { 
                last = last.nextdata; 
            } 
  
            // add the newdata at end 
            last.nextdata = newdata; 
        } 
  
        // Return the list 
        return list; 
    } 
  
    // Method to print the LinkedList. 
    public static void printnodes() 
    { 
        Node currentNode = list.head; 
        System.out.print("LinkedList: "); 
   
        // Traverse the LinkedList 
        while (currentNode != null) { 
            // Print the data at current node 
            System.out.print(currentNode.data + " "); 
   
            // Go to nextdata node 
            currentNode = currentNode.nextdata; 
        } 
    } 
        
        // Method to find the last element 
        // whose index is multiple of given number
        public static void lastK(int k)
        {
                int index = 0;    // take first index as 0
                Node currentNode = list.head;
                int element = 0;        
                
                // check if the list is empty
                if(currentNode == null)
                {
                        System.out.println("\nList is empty");
                }
                else
                {
                        // if the list is not empty, take first value of list as element
                        element = currentNode.data;
                        
                        // traverse the list 
                        while (currentNode != null) { 
                                // Print the data at current node 
                                // if the index value is divisible by k,
                                // update the value of element with the current node value
                                if(index%k==0)
                                        element = currentNode.data;
                                
                                // increment the index value
                                index++;
   
                                // Go to nextdata node 
                                currentNode = currentNode.nextdata; 
                        }
                        
                        // print the answer
                        System.out.println("\nLast element whose index is multiple of "+k+" = "+element);
        } 
                
        }
        
        // main method
    public static void main(String[] args) throws IOException
    {           
        
                // create BufferedReader to take input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                
                // input number of nodes in the linked list
                System.out.println("Enter number of nodes in linked list:");
                int n = Integer.parseInt(br.readLine());
                
                // input nodes using for loop
                System.out.println("Enter nodes:");
                for(int i=0;i<n;i++){
                        int x = Integer.parseInt(br.readLine());
                        
                        // add node in linked list
                        list = add(list,x);
                }
                
                // input value of k
                System.out.println("Enter value of k:");
                int k = Integer.parseInt(br.readLine());
  
        
        // Print the LinkedList 
        printnodes();
                // find the node whose index is multiple of given number
                lastK(k);
    } 
} 

In finding the last element with index multiple of k, we are scanning the list from starting to end one time, so the time complexity of the algorithm is O(n), where n is the number of nodes present in linked list.

Space complexity will be O(1) because we are using only one variable to store the result.

Function screenshot

Output screenshot: