Last Updated on November 22, 2022 by Prepbytes
The Linked list is an important topic from an interview perspective. Companies like Amazon, Flipkart, Goldman Sach, Abode, Samsung, and many more asked questions over the linked lists. In this blog, we will discuss the famous problem of the linked list “find the sum of last n nodes of the linked list”. Let’s deep dive and solve “sum of nodes in linked list”.
We will be given a linked list and a number n as input and we need to find the 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 To Find The Sum Of Last N Nodes Of The Linked List :
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 To Find The Sum Of Last N Nodes Of The Linked List – 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 To Find The Sum Of Last N Nodes Of The Linked List:
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 To Find The Sum Of Last N Nodes Of The Linked List:
#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: 58Time Complexity To Find The Sum Of Last N Nodes Of The Linked List – O(n)
Note that although the complexity of this approach is the same as the previous one, we are traversing the list only once in this approach rather than traversing twice.
This blog had solved and discussed completely to find the sum of last n nodes of the linked list. This problem tests a candidate’s problem-solving skills and his or her grasp on the concepts of linked list and heap. We highly encourage you to have a good grasp of major data structures. If you want to practice more questions on linked lists, feel free to solve them at PrepBytes Linked List.
FAQ
1. How do you find the last node in a linked list?
The last node of a linked list has the reference pointer as NULL. i.e. node=>next = NULL. To find the last node, we have to iterate the linked till the node=>next != NULL.
2. How do you sum nodes in a linked list?
So to find the sum of all elements of the singly linked list, we have to navigate to each node of the linked list and add the element’s value to a sum variable. Suppose we have a linked list: 5 -> 30 -> 32 -> 1 -> 9 sum = 5 + 30 + 32 + 1 + 9 = 77.
3. What is the last node in a linked list called?
The first node in the list is called the head, and the last node in the list is called the tail. To create a singly linked list, we first need to create a node class. Each node will have two data members: an integer value and a reference to the next node in the list.