Find the Sum of Last N Node of given Linked List

Approach

As we read the problem statement to find the sum of the last n node of the Linked List, we get the following steps for solving the problem, which are listed below:

1. Create a Linked List.
2. Find the length of the Linked List.
3. We are finding the length of the Linked List because we have to find the last n node sum for which we have the value of n, and from the getlength() function, we get the length of the linked list.
4. From step-3, we have n and len both; then, we have to find the sum of linked list nodes from node number len-n+1 to the last node of k linked list.
5. We run a loop from i=1 to I <(len-n+1) value to skip the nodes and move forward just from starting to (len-n) point.
6. After that, whatever the nodes present from nodes number len-n+1 to end is the value of last n nodes, then we run a loop till the value of node!=null, and accumulate the data of each node by adding it.
7. At last, when we have found that the current node value is null, then we come out from the loop, and we get our answer as the sum of the last n node.

These all above 7 steps we perform we find the sum of the last n nodes of the Linked List.

Code

import java.util.Scanner;

public class sum_last_n_node {
  // Declaring the Node class for creating linked list
  class Node{
      int data;
      Node next;
public Node(int data){
          this.data=data;
          next=null;
      }
  }
  Node head=null;
  Node tail=null;
  // Creating getlength function to find the length of the Linked List
  public int getlength(){
      Node curr=head;
      // Declare count variable for maintaining the number of Nodes in Linked List
      int count=0;
      // Iterate to the end of the last node to find length
      while(curr!=null){
          count++;
          curr=curr.next;
      }
      return count;
  }
  // Creating the getsum function to find the sum of last n node of Linked List
  public int getsum(int len,int last_n){
      int sum=0;
      // finding the location of node number before that all node are to skip
      int val=len-last_n+1;
      Node curr=head;
      int i=1;
      // Run a while loop for skip the node for not to be part of sum
      while(i<val){
          curr=curr.next;
          i++;
      }
      // Run a while loop after skipping the node , after that
      // all the values of nodes are part of the answer.
      while (curr!=null){
          // Summing the value of curr nodes data and just accumulating it
          sum+=curr.data;
          curr=curr.next;
      }
      // After the complete accumulation just we return the value of accumulated sum
      return sum;
  }
  // Creating a push function for pushing the data in the created Linked List.
  public void push(int data){
      Node newNode=new Node(data);
      if(head==null){
          head=tail=newNode;
          tail.next=null;
      }
      else{
          tail.next=newNode;
          tail=newNode;
          tail.next=null;
      }

  }
  // Creating the print function for printing the created Linked List
  public void print(){
      Node curr=head;
      if(curr==null){
          System.out.println("Linked List is Empty ! kindly insert data in it .");
          return;
      }
      while(curr!=null){
          System.out.print(curr.data+" ");
          curr=curr.next;
      }
  }
  // Driver code for running all the functions above created.
  public static void main(String []args){
      sum_last_n_node element=new sum_last_n_node();
      element.push(7);
      element.push(2);
      element.push(4);
      element.push(23);
      element.push(31);
      System.out.println("The given element in the Linked List are: ");
      element.print();
      System.out.println();
      System.out.println("Enter the value of n for the the last n node sum in the Linked List !");
      Scanner sc=new Scanner(System.in);
      int last_n=sc.nextInt();
      System.out.println("Enter value of n here is : "+ last_n);
      System.out.println();
      int len=element.getlength();
      int ans=element.getsum(len,last_n);
      System.out.println("The sum of last n node of the linked list is : "+ ans);
  }
}

You can also try this code with Online Java Compiler

Run Code

Dry-Run

Now for the dry-run for the above, take a simple above example again with the value of n to be 3, which means we have given a linked list, and we have to find the sum of the last nodes of the Linked List.

Here is the representation of the created Linked List, and we have to find the sum of the last 3 nodes 4+23+31=58.

Now understand the solution with the help of a dry-run of the above code implementation:

1. Firstly we have created a Node class which has data as an integer for storing the integer value of Linked list and node as next for storing the address of the next node pointing to next.
2. In the next step, we create a push function to insert more newNode in the linked list.
3. First, we push 7, as head==null now we initialise head=newNode=7 and declare tail to move to the next node for, and leave the head as reference for the first node for accessing all the nodes from start to end.
4. For the second time, 2 is pushed, then we see the head!=7 as head=7. For that, we have to move the tail.next=newNode, tail=newNode and tail.next=null; we repeat the step to push for the nodes 4, 23 and 31 similarly.
5. Now, we have created the singly linked list. To see the Linked List, we now created a function called print.
6. In the print function, we declare another node curr and instailized value of head, Now we iterate till we find the nodes, as curr!=null and print the data of each of the nodes as curr.data and move to the next node as curr=curr.next.
   1. Node we find after call of print as 7->2->4->23->31.
7. Now we created another function getlength, to find the length of the Linked List; in the getlength function, we declare count variable to keep track of how many nodes we have visite after each visit of the nodes we directly increase the counter for the count variable and move to the next node we repeat till we encounter curr!=null. After that, we get the length of the linked list to be 5.
8.  After we get the value of the length of the Linked List from the getlength function, we have to find the point where we have to skip so that we have to find the sum of the last node we see. After that, we have the length value of len and value last n node as last_n from the user. The len=5 and last_n=3.
9. After that, we find (len-last_n)=(5-3)=2 value indicating the number of nodes we have to skip; then we have to find the sum from (len-last_n+1)=(5-3+1)=3 value of nodes number.
10.  Now we call the getsum function to find the sum of the last n node of Linked List.
11. In the getsum function firstly, we initialized i to be 0; then through the while loop, we skip all the nodes to be skipped for the answer for the solution as curr=curr.next till i<(len-last_n+1) or val or 3 .We just skip the node 7 and 2 only.
12. Now from the next node, we have declared a variable called sum, where we have to start iterating through the node from (len-last_n+1) node, then adding the sum+=curr.data and moving to the next node as curr=curr.next, we get sum =4+23+31, when we get curr!=null, then we return the value of sum, which is the sum of the last n node of the given linked list. Hence we return 4+23+31=58 from the value store in the sum variable.

Complexity Analysis

The Time Complexity of the above code is O(n), and the Space Complexity of the Above code is O(1).

Time Complexity

we see we create the linked list, which takes O(1) for attaching the node to the next node now. For finding the length of the Linked List, we are traversing the total number of node present in it, O(L), where L is the total length of the singly linked list, then for getsum function, we are skipping len-last_n node then adding len-last_n+1 node which generally same as the length of the linked list, so it's also done in O(L), so in order to print the Linked list we are traversing the length of the linked list, which done in O(L) if take N=L as the length of the list(N(getsum)+N(print)+N(getlength)+1(addNode))

So we have the Time Complexity as (3*N+1) where O(N) is the Time Complexity.

Space Complexity

we are doing all the operation like getsum, getlength, and print of the Linked List on the same created Linked List; we just using extra node curr which occupy O(1) memory for just traversing the Linked List, so we have the Space Complexity is O(1).
Check out this problem - Subarray Sum Divisible By K

Frequently Asked Questions

What is Time Complexity and Space Complexity?

Time Complexity is O(N), and Space Complexity is O(1).

What is a Singly Linked List?

The singly linked list address field of the last node must contain a NULL value specifying the end of the list. Each node of a singly linked list follows a common basic structure. In a node, we can store more than one data field, but we need at least a single address field to store the address of the following connected node.

How much memory is used when allocating a linked list in Java?

If each block occupies 8-byte memory, then in the singly linked list, it stores the data and pointer to the next node, which in total 8*2=16 byte.

Conclusion

In this blog, we have understood the way of working with a singly Linked List, finding the sum of the last n node of the linked list, and understanding the concept of finding the length of the singly Linked List. From doing all this, at last, we get our task done with the Time Complexity of O(N), and Space Complexity is O(1).

Recommended Readings:

• Lenght of a Linked List
• Linked Lists in Python
• Popular Data Structure Problems
   

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, etc. as well as some Contests and Interview Experiences curated by top Industry Experts only on  Coding Ninjas Studio.

Happy Learning Ninja!