Find the sum of last n nodes of the given Linked List

We will be given a linked list and a number n as input and we need to find sum of the last n nodes of the linked list.

Let the input be the list given below and n = 3.

The output of the above input will be:- 58 [sum of last 3 nodes data i.e. 4,23,31]

Approach #1 :

In this approach,

  • we first calculate the length of the linked list and let it be L.
  • Then, we move a pointer (initially at head ) to (L - n) nodes forward from its initial position.
  • Then, traverse the remaining nodes while adding their values in a variable and return the sum variable.

Time Complexity - O(n)

The above approach seems good but we could do even better because we are traversing the list twice in the above approach and we could reduce it to traversing the list just once. Let’s learn to do this in second approach below.

Approach #2 :

In this approach,

  • Create 2 pointers initially pointing to the head of the linked list.
  • Move one pointer n nodes away from the head and accumulate sum while moving it in a variable (say sum).
  • Now move both pointers by one node simultaneously till the pointer moved in step 2 becomes NULL and accumulate the sum of nodes for both the pointers in separate variables.
  • Now the pointer that is ahead, has sum of all nodes of the list and the pointer that is behind, has sum of (L-n) nodes of the list (where L is the length of the linked list). So, we need to subtract both variables in order to get our result.

Code Implementation:

Find the sum of last n nodes of the given Linked List


#include
Using namespace std;

class Node
{
    public:
    int data;
    Node* next;
    Node(int x){
        data = x;
   next = NULL;
    }
};
 
int sum_of_last_N_nodes( Node* head, int n)
{
    if (n <= 0)
        return 0;
 
    int sum = 0, temp = 0;
    Node* right_pointer, *left_pointer;
    right_pointer = left_pointer = head;
 
    // moving the right pointer n nodes to the right from head
    // as discussed in step 2
    while (right_pointer != NULL &&  n>0) {                  
        sum += right_pointer->data;
        n--;
        right_pointer = right_pointer->next;
    }
 
    // traversing the list by moving both the pointers 
    // simultaneously till right pointer reaches end
    while (right_pointer != NULL) {
 
        // store all node's data in 'temp' pointed
        // by the 'left_pointer'
        temp += left_pointer->data;
 
        // store all node's data to 'sum' pointed by
        // the 'right_pointer'
        sum += right_pointer->data;
 
        left_pointer = left_pointer->next;
        right_pointer = right_pointer->next;
    }
 
    // return the difference in both variables as discussed in
    // last step
    return (sum - temp);
}
 
int main(void)
{
    Node* head = NULL;
    head = new Node(7);
    head->next = new Node(2);
    head->next->next = new Node(4);
    head->next->next->next = new Node(23);
    head->->next->next->next->next = new Node(31);
 
    cout<

						 

Output
58

Time Complexity - O(n)

Note that although the complexity of this approach is the same as previous one, we are traversing the list only once in this approach rather than traversing twice.

So, in this blog, we have tried to explain how you can find the sum of the last n nodes of a given linked list in the most optimal way. If you want to practice more questions on the linked list, feel free to do so at Prepbytes Linked List.

Previous post Remove all occurrences of duplicates from a sorted Linked List
Next post Reverse a Doubly Linked List

Leave a Reply

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