Linked List: Sum of last N nodes

Question: Write a function that returns the sun of the last N nodes of a linked list. For example. for the linked list 4->6->10->8->9->10->18->20, and the value of N=4 the answer would be 57.

package additional_problems.linkedList;

/**
 * Created by aarushi on 29/6/21.
 */
public class P07SumOfLastN {

    public static void main(String [] args){
        //create a linked list
        LinkedList list= new LinkedList();
        ListNode node= new ListNode(4);
        list.add(node);
        node= new ListNode(6);
        list.add(node);
        node= new ListNode(10);
        list.add(node);
        node= new ListNode(8);
        list.add(node);
        node= new ListNode(9);
        list.add(node);
        node= new ListNode(10);
        list.add(node);
        node= new ListNode(18);
        list.add(node);
        node= new ListNode(20);
        list.add(node);

        //call the method to calculate sum of the last n nodes and print the value returned
        System.out.println(sumOfLastNNodes(list, 4));

    }

    //method to find the sum of the last n nodes
    public static int sumOfLastNNodes(LinkedList list, int n){
        //length: contains the length of the linked list
        //numOfElements: contains the index from which the sum has to be calculated
        //index: will keep track of which index the pointer is at
        //sum: will store the sum of the node values
        int length= list.findLength(), numOfElement= length-n, index=0, sum=0;
        
        //temp: pointer that will traverse through the linked list
        ListNode temp= list.head;

        //traverse the array till the node from which the sum has to be calculated is reached
        while(temp!=null && index!=numOfElement){
            index++;
            temp=temp.getNext();
        }

        //calculate the sum of each node value till the end of the linked list
        while (temp!=null){
            sum+=temp.getData();
            temp=temp.getNext();
        }

        //return the sum
        return sum;
    }
}
package additional_problems.linkedList;

/**
 * Created by aarushi on 24/6/21.
 */
public class LinkedList {
    //data fields
    //head node
    ListNode head;

    //constructor to initialize head node
    public LinkedList() {
        head = null;
    }

    //function to add node to the end of the linked list
    public void add(ListNode node) {
        //if list is empty then set head equal to the node
        if (head == null) {
            head = node;
            node.setNext(null);
        } else {
            //create a pointer- temp
            ListNode temp = head;
            //iterate to the last element
            while (temp.getNext() != null) {
                temp = temp.getNext();
            }
            //insert the node at the end of the list
            temp.setNext(node);
            node.setNext(null);
        }
    }
}
package additional_problems.linkedList;

/**
 * This class is the type declaration for a linked list
 * Created by aarushi on 24/6/21.
 */
public class ListNode {
    //data fields
    private int data; //stores the value of the node
    private ListNode next; //stores the reference of the next node

    //constructor to initialize the value of the node
    public ListNode(int data){
        this.data= data;
        this.subList=null;
    }

    //accessor method to get the value stored in data
    public int getData() {
        return this.data;
    }

    //mutator method to change the value of data
    public void setData(int data) {
        this.data = data;
    }

    //accessor method which returns the reference of the next node
    public ListNode getNext() {
        return this.next;
    }

    //mutator method which changes the reference of the next node
    public void setNext(ListNode next) {
        this.next = next;
    }

}

Leave a Reply

PHP JS HTML CSS BASH PYTHON CODE

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this:
search previous next tag category expand menu location phone mail time cart zoom edit close