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:

#include<stdio.h>
#include<stdlib.h>

struct Node {
    int data;
    struct Node* next;
};
 
// function to insert a node at the
// beginning of the linked list
void push(struct Node** head_ref, int new_data)
{
    /* allocate node */
    struct Node* new_node = malloc(sizeof(struct Node*));
 
    /* put in the data  */
    new_node->data = new_data;
 
    /* link the old list to the new node */
    new_node->next = (*head_ref);
 
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
// function to recursively find the sum of last
// 'n' nodes of the given linked list
void sumOfLastN_Nodes(struct Node* head, int* n,
                                      int* sum)
{
    // if head = NULL
    if (!head)
        return;
 
    // recursively traverse the remaining nodes
    sumOfLastN_Nodes(head->next, n, sum);
 
    // if node count 'n' is greater than 0
    if (*n > 0) {
 
        // accumulate sum
        *sum = *sum + head->data;
 
        // reduce node count 'n' by 1
        --*n;
    }
}
 
// utility function to find the sum of last 'n' nodes
int sumOfLastN_NodesUtil(struct Node* head, int n)
{
    // if n == 0
    if (n <= 0)
        return 0;
 
    int sum = 0;
 
    // find the sum of last 'n' nodes
    sumOfLastN_Nodes(head, &n, &sum);
 
    // required sum
    return sum;
}
 
// Driver program to test above
int main()
{
    struct Node* head = NULL;
 
    // create linked list 10->6->8->4->12
    push(&head, 12);
    push(&head, 4);
    push(&head, 8);
    push(&head, 6);
    push(&head, 10);
 
    int n = 2;
    int ans = sumOfLastN_NodesUtil(head, n);
	printf("Sum of last n Nodes %d",ans);
    return 0;
}

#include<bits/stdc++.h>
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<<sum_of_last_n_nodes(head,3); 
    return 0;
}
class sum
{
	static class Node
	{
		int data;
		Node next;
	}

	static Node head;

	static void printList(Node start)
	{
		Node temp = start;
		while (temp != null)
		{
			System.out.print(temp.data + " ");
			temp = temp.next;
		}
		System.out.println();
	}
	static void push(Node start, int info)
	{
		Node node = new Node();
		node.data = info;
		node.next = start;
		head = node;
    }
	static int sumOfLastN_NodesUtil(Node head, int n)
	{
		if (n <= 0)
			return 0;

		int sum = 0, temp = 0;
		Node ref_ptr, main_ptr;
		ref_ptr = main_ptr = head;

		// traverse 1st 'n' nodes through 'ref_ptr' and accumulate all node's data to 'sum'
		while (ref_ptr != null && (n--) > 0)
		{
			sum += ref_ptr.data;
			ref_ptr = ref_ptr.next;
		}
		while (ref_ptr != null)
		{
			temp += main_ptr.data;
			sum += ref_ptr.data;
			main_ptr = main_ptr.next;
			ref_ptr = ref_ptr.next;
		}
		return (sum - temp);
	}
	public static void main(String[] args)
	{
		head = null;

		push(head, 12);
		push(head, 4);
		push(head, 8);
		push(head, 6);
		push(head, 10);

		printList(head);

		int n = 3;

		System.out.println("Sum of last " + n +" nodes = " + sumOfLastN_NodesUtil(head, n));
	}
}



class Node:

	def __init__(self, data):
		self.data = data
		self.next = None

def sum_of_last_n_nodes( head, n):

	if n<=0:
		return 0

	sum = 0
	temp = 0
	right = left = head
	while right and n>0:
		sum += right.data
		n -= 1
		right = right.next

	while right:
		temp += left.data
		sum +=right.data
		left = left.next
		right = right.next
	return sum - temp

head = None
head = Node(7)
head.next = Node(2)
head.next.next = Node(4)
head.next.next.next = Node(23)
head.next.next.next.next = Node(31)

print(sum_of_last_n_nodes(head,3))

Output
58

Time Complexity – O(n)
[forminator_quiz id=”3431″]

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.

Leave a Reply

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