Search⌘ K
Home
Courses
Recursion for Coding Interviews in C++

Sum Numbers in a Linked List

Explore how recursion can be applied to linked lists to sum all node values in this lesson. Understand the role of the base case and recursive case in a recursive function, and see the problem solved step-by-step with clear code examples. This lesson builds your ability to manipulate data structures recursively in C++.

We'll cover the following...

Sum n Numbers

Given a linked list, add numbers and then return the sum. The following illustration explains the concept:

Implementing the Code

The following code calculates the sum of the node values in the linked list using recursion.

Experiment with the following code by changing the elements of the list.

C++
#include<iostream>
using namespace std; 
  
// Node Class
class Node  
{  
    public: 
    int data;  
    Node *next;  
};  
  
  
//calculate sum of numbers in a linked list
int sumList(Node* head)
{ //base case 
  if (head == NULL) return 0;
  //recursive case
   else return head->data + sumList (head->next);
}
  
//insert a new node
void insertAtHead(Node** head, int new_data)  
{  
    //make a new node
    Node* new_node = new Node(); 
      
    //insert data in the node
    new_node->data = new_data;  
      
   //make the new_node->next points to head
    new_node->next = (*head);  
      
    //head points at new node
    (*head) = new_node;  
}  
  
//Driver Function
int main()  
{  
    //emty list
    Node* head = NULL;  
      
    //insert Data in the list
    insertAtHead(&head, 5);  
    insertAtHead(&head, 4);  
    insertAtHead(&head, 3);  
    insertAtHead(&head, 2);  
    insertAtHead(&head, 1);  
      
    cout<<"List:1->2->3->4->5 \n Sum of numbers in a list:";  
    cout<<sumList(head);  
  
    return 0;  
}

Understanding the Code

A recursive code can be broken down into two ...