js

Saturday, August 27, 2022

 

Write a Program to Find the Maximum Depth or Height of a Tree

  • Difficulty Level : Easy
  • Last Updated : 21 Jul, 2022

Given a binary tree, find height of it. Height of empty tree is -1, height of tree with one node is 0 and height of below tree is 2. 


 

Example Tree

 

 

 

Recursively calculate height of left and right subtrees of a node and assign height to the node as max of the heights of two children plus 1. See below pseudo code and program for details.
Algorithm: 

 maxDepth()
1. If tree is empty then return -1
2. Else
     (a) Get the max depth of left subtree recursively  i.e., 
          call maxDepth( tree->left-subtree)
     (a) Get the max depth of right subtree recursively  i.e., 
          call maxDepth( tree->right-subtree)
     (c) Get the max of max depths of left and right 
          subtrees and add 1 to it for the current node.
         max_depth = max(max dept of left subtree,  
                             max depth of right subtree) 
                             + 1
     (d) Return max_depth

See the below diagram for more clarity about execution of the recursive function maxDepth() for above example tree. 

            maxDepth('1') = max(maxDepth('2'), maxDepth('3')) + 1
                               = 1 + 1
                                  /    \
                                /         \
                              /             \
                            /                 \
                          /                     \
               maxDepth('2') = 1                maxDepth('3') = 0
= max(maxDepth('4'), maxDepth('5')) + 1
= 1 + 0   = 1         
                   /    \
                 /        \
               /            \
             /                \
           /                    \
 maxDepth('4') = 0     maxDepth('5') = 0

Implementation: 

Output
Height of tree is 2

Time Complexity: O(n) (Please see our post Tree Traversal for details)

Auxiliary Space: O(n) due to recursive calls.
 

Method 2: Another method to solve this problem is to do Level Order Traversal. While doing the level order traversal, while adding Nodes at each level to Queue, we have to add NULL Node so that whenever it is encountered, we can increment the value of variable and that level get counted.

Implementation:

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
 
// A Tree node
struct Node
{
    int key;
    struct Node* left, *right;
};
   
// Utility function to create a new node
Node* newNode(int key)
{
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return (temp);
}
   
/*Function to find the height(depth) of the tree*/
int height(struct Node* root){
 
    //Initialising a variable to count the
      //height of tree
      int depth = 0;
   
    queue<Node*>q;
     
      //Pushing first level element along with NULL
      q.push(root);
    q.push(NULL);
    while(!q.empty()){
        Node* temp = q.front();
        q.pop();
       
          //When NULL encountered, increment the value
        if(temp == NULL){
            depth++;
        }
           
          //If NULL not encountered, keep moving
        if(temp != NULL){
            if(temp->left){
                  q.push(temp->left);
            }
              if(temp->right){
                q.push(temp->right);
            }
        }
       
          //If queue still have elements left,
          //push NULL again to the queue.
        else if(!q.empty()){
            q.push(NULL);
        }
    }
    return depth;
}
 
// Driver program
int main()
{
    // Let us create Binary Tree shown in above example
    Node *root  = newNode(1);
    root->left  = newNode(12);
    root->right = newNode(13);
   
    root->right->left   = newNode(14);
    root->right->right  = newNode(15);
   
    root->right->left->left   = newNode(21);
    root->right->left->right  = newNode(22);
    root->right->right->left  = newNode(23);
    root->right->right->right = newNode(24);
   
      cout<<"Height(Depth) of tree is: "<<height(root);
}
Output
Height(Depth) of tree is: 4

Time Complexity: O(n)

Auxiliary Space: O(n)

Method 3: This method also uses the concept of Level Order Traversal but we wont be adding null in the Queue. We will simply increase the counter when the level will increase and then remove all the nodes from the queue of the current Level.

// Java program for above approach
import java.util.LinkedList;
import java.util.Queue;
 
class GFG {
 
// A tree node structure
static class Node {
    int key;
    Node left;
    Node right;
}
 
// Utility function to create
// a new node
static Node newNode(int key) {
    Node temp = new Node();
    temp.key = key;
    temp.left = temp.right = null;
    return temp;
}
 
 
/*Function to find the height(depth) of the tree*/
public static int height( Node root){
 
    //Initialising a variable to count the
    //height of tree
     Queue<Node>q=new LinkedList<Node>();
        q.add(root);
        int height=0;
        while(!q.isEmpty()){
            int size=q.size();
            for(int i=0;i<size;i++){
                Node temp=q.poll();
                if(temp.left!=null){
                    q.add(temp.left);
                }
                if(temp.right!=null){
                    q.add(temp.right);
                }
            }
            height++;
            
        }
        return height;
}
 
 
 
// Driver Code
public static void main(String args[]) {
    Node root  = newNode(1);
    root.left  = newNode(12);
    root.right = newNode(13);
   
    root.right.left   = newNode(14);
    root.right.right  = newNode(15);
   
    root.right.left.left   = newNode(21);
    root.right.left.right  = newNode(22);
    root.right.right.left  = newNode(23);
    root.right.right.right = newNode(24);
   
    System.out.println("Height(Depth) of tree is: "+height(root));
 
    }
}
Output
Height(Depth) of tree is: 4

Time Complexity: O(n)

Auxiliary Space: O(n)

Invert/Mirror binary tree

 

Mirror of a Tree: Mirror of a Binary Tree T is another Binary Tree M(T) with left and right children of all non-leaf nodes interchanged. 
 

MirrorTree1

Trees in the above figure are mirror of each other


Method 1 (Recursive)

Algorithm – Mirror(tree): 

(1)  Call Mirror for left-subtree    i.e., Mirror(left-subtree)
(2)  Call Mirror for right-subtree  i.e., Mirror(right-subtree)
(3)  Swap left and right subtrees.
          temp = left-subtree
          left-subtree = right-subtree
          right-subtree = temp

Implementation:

// C++ program to convert a binary tree
// to its mirror
#include<bits/stdc++.h>
using namespace std;
  
/* A binary tree node has data, pointer 
to left child and a pointer to right child */
struct Node 
{
    int data;
    struct Node* left;
    struct Node* right;
};
  
/* Helper function that allocates a new node with 
the given data and NULL left and right pointers. */
struct Node* newNode(int data)
{
    struct Node* node = (struct Node*)
                         malloc(sizeof(struct Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
      
    return(node);
}
  
  
/* Change a tree so that the roles of the left and 
    right pointers are swapped at every node.
  
So the tree...
    4
    / \
    2 5
    / \
1 3
  
is changed to...
    4
    / \
    5 2
        / \
    3 1
*/
void mirror(struct Node* node) 
{
    if (node == NULL) 
        return; 
    else
    {
        struct Node* temp;
          
        /* do the subtrees */
        mirror(node->left);
        mirror(node->right);
      
        /* swap the pointers in this node */
        temp     = node->left;
        node->left = node->right;
        node->right = temp;
    }
} 
  
/* Helper function to print 
Inorder traversal.*/
void inOrder(struct Node* node) 
{
    if (node == NULL) 
        return;
      
    inOrder(node->left);
    cout << node->data << " ";
    inOrder(node->right);
} 
  
  
// Driver Code
int main()
{
    struct Node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5); 
      
    /* Print inorder traversal of the input tree */
    cout << "Inorder traversal of the constructed"
         << " tree is" << endl;
    inOrder(root);
      
    /* Convert tree to its mirror */
    mirror(root); 
      
    /* Print inorder traversal of the mirror tree */
    cout << "\nInorder traversal of the mirror tree"
         << " is \n"; 
    inOrder(root);
      
    return 0; 
}
  
// This code is contributed by Akanksha Rai

Output:  

Inorder traversal of the constructed tree is 
4 2 5 1 3 
Inorder traversal of the mirror tree is 
3 1 5 2 4 

Time & Space Complexities: Worst-case Time complexity is O(n) and for space complexity, If we don’t consider the size of the recursive stack for function calls then O(1) otherwise O(h) where h is the height of the tree.  This program is similar to traversal of tree space and time complexities will be the same as Tree traversal more for information Please see our Tree Traversal post for details.

Method 2 (Iterative): The idea is to do queue based level order traversal. While doing traversal, swap left and right children of every node.
Implementation:

// Iterative CPP program to convert a Binary
// Tree to its mirror
#include<bits/stdc++.h>
using namespace std;
  
/* A binary tree node has data, pointer to
   left child and a pointer to right child */
struct Node
{
    int data;
    struct Node* left;
    struct Node* right;
};
  
/* Helper function that allocates a new node
   with the given data and NULL left and right
   pointers. */
struct Node* newNode(int data)
  
{
    struct Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return(node);
}
  
/* Change a tree so that the roles of the  left and
    right pointers are swapped at every node.
 So the tree...
       4
      / \
     2   5
    / \
   1   3
  
 is changed to...
       4
      / \
     5   2
        / \
       3   1
*/
void mirror(Node* root)
{
    if (root == NULL)
        return;
  
    queue<Node*> q;
    q.push(root);
  
    // Do BFS. While doing BFS, keep swapping
    // left and right children
    while (!q.empty())
    {
        // pop top node from queue
        Node* curr = q.front();
        q.pop();
  
        // swap left child with right child
        swap(curr->left, curr->right);
  
        // push left and right children
        if (curr->left)
            q.push(curr->left);
        if (curr->right)
            q.push(curr->right);
    }
}
  
  
/* Helper function to print Inorder traversal.*/
void inOrder(struct Node* node)
{
    if (node == NULL)
        return;
    inOrder(node->left);
    cout << node->data << " ";
    inOrder(node->right);
}
  
  
/* Driver program to test mirror() */
int main()
{
    struct Node *root = newNode(1);
    root->left        = newNode(2);
    root->right       = newNode(3);
    root->left->left  = newNode(4);
    root->left->right = newNode(5);
  
    /* Print inorder traversal of the input tree */
    cout << "\n Inorder traversal of the"
            " constructed tree is \n";
    inOrder(root);
  
    /* Convert tree to its mirror */
    mirror(root);
  
    /* Print inorder traversal of the mirror tree */
    cout << "\n Inorder traversal of the "
           "mirror tree is \n";
    inOrder(root);
  
    return 0;
}

Output: 

 Inorder traversal of the constructed tree is 
4 2 5 1 3 
 Inorder traversal of the mirror tree is 
3 1 5 2 4 

Count duplicates in a given linked list

 

Given a linked list. The task is to count the number of duplicate nodes in the linked list. 
Examples: 
 

Input: 5 -> 7 -> 5 -> 1 -> 7 -> NULL 
Output: 2
Input: 5 -> 7 -> 8 -> 7 -> 1 -> NULL 
Output: 1 
 

 

Simple Approach: We traverse the whole linked list. For each node we check in the remaining list whether the duplicate node exists or not. If it does then we increment the count.
Below is the implementation of the above approach: 
 

// C++ implementation of the approach
#include <iostream>
#include <unordered_set>
using namespace std;
 
// Representation of node
struct Node {
    int data;
    Node* next;
};
 
 
// Function to insert a node at the beginning
void insert(Node** head, int item)
{
    Node* temp = new Node();
    temp->data = item;
    temp->next = *head;
    *head = temp;
}
 
// Function to count the number of
// duplicate nodes in the linked list
int countNode(Node* head)
{
    int count = 0;
 
    while (head->next != NULL) {
 
        // Starting from the next node
        Node *ptr = head->next;
        while (ptr != NULL) {
 
            // If some duplicate node is found
            if (head->data == ptr->data) {
                count++;
                break;
            }
            ptr = ptr->next;
        }
 
        head = head->next;
    }
 
    // Return the count of duplicate nodes
    return count;
}
 
// Driver code
int main()
{
    Node* head = NULL;
    insert(&head, 5);
    insert(&head, 7);
    insert(&head, 5);
    insert(&head, 1);
    insert(&head, 7);
 
    cout << countNode(head);
 
    return 0;
}
Output: 
2

 

Time Complexity: O(n*n)
Efficient Approach: The idea is to use hashing 
 

// C++ implementation of the approach
#include <iostream>
#include <unordered_set>
using namespace std;
 
// Representation of node
struct Node {
    int data;
    Node* next;
};
 
// Function to insert a node at the beginning
void insert(Node** head, int item)
{
    Node* temp = new Node();
    temp->data = item;
    temp->next = *head;
    *head = temp;
}
 
// Function to count the number of
// duplicate nodes in the linked list
int countNode(Node* head)
{
    if (head == NULL)
       return 0;;
 
    // Create a hash table insert head
    unordered_set<int> s;
    s.insert(head->data);
 
    // Traverse through remaining nodes   
    int count = 0;
    for (Node *curr=head->next; curr != NULL; curr=curr->next) {
        if (s.find(curr->data) != s.end())
             count++;
 
        s.insert(curr->data);
    }
 
    // Return the count of duplicate nodes
    return count;
}
 
// Driver code
int main()
{
    Node* head = NULL;
    insert(&head, 5);
    insert(&head, 7);
    insert(&head, 5);
    insert(&head, 1);
    insert(&head, 7);
 
    cout << countNode(head);
 
    return 0;
}
Output: 
2

 

Time Complexity : O(n)

Add two numbers represented by linked lists

 


  • Difficulty Level : Easy
  • Last Updated : 05 Jul, 2022

Given two numbers represented by two lists, write a function that returns the sum list. The sum list is a list representation of the addition of two input numbers.

Example:

Input: 
List1: 5->6->3 // represents number 563 
List2: 8->4->2 // represents number 842 
Output: 
Resultant list: 1->4->0->5 // represents number 1405 
Explanation: 563 + 842 = 1405

Input: 
List1: 7->5->9->4->6 // represents number 75946
List2: 8->4 // represents number 84
Output: 
Resultant list: 7->6->0->3->0// represents number 76030
Explanation: 75946+84=76030

Approach: Traverse both lists to the end and add preceding zeros in the list with lesser digits. Then call a recursive function on the start nodes of both lists which calls itself for the next nodes of both lists till it gets to the end. This function creates a node for the sum of the current digits and returns the carry. 

 

Complete Interview Preparation - GFG

The steps are: 

  1. Traverse the two linked lists in order to add preceding zeros in case a list is having lesser digits than the other one.
  2. Start from the head node of both lists and call a recursive function for the next nodes.
  3. Continue it till the end of the lists.
  4. Creates a node for current digits sum and returns the carry.

Below is the implementation of this approach. 

// C++ program to add two numbers
// represented by linked list
#include <bits/stdc++.h>
using namespace std;
 
/* Linked list node */
class Node {
public:
    int data;
    Node* next;
};
 
/* Function to create a
new node with given data */
Node* newNode(int data)
{
    Node* new_node = new Node();
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}
 
/* Function to insert a node at the
beginning of the Singly Linked List */
void push(Node** head_ref, int new_data)
{
    /* allocate node */
    Node* new_node = newNode(new_data);
    /* link the old list off the new node */
    new_node->next = (*head_ref);
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
/* Adds contents of two linked lists and
return the head node of resultant list */
Node* addTwoLists(Node* first, Node* second)
{
    // res is head node of the resultant list
    Node* res = NULL;
    Node *temp, *prev = NULL;
    int carry = 0, sum;
 
    // while both lists exist
    while (first != NULL || second != NULL) {
        // Calculate value of next digit in resultant list.
        // The next digit is sum of following things
          // (i) Carry
        // (ii) Next digit of first list (if there is a next digit)
        // (ii) Next digit of second list (if there is a next digit)
        sum = carry + (first ? first->data : 0) + (second ? second->data : 0);
        // update carry for next calculation
        carry = (sum >= 10) ? 1 : 0;
        // update sum if it is greater than 10
        sum = sum % 10;
        // Create a new node with sum as data
        temp = newNode(sum);
        // if this is the first node then set it as head of the resultant list
        if (res == NULL)
            res = temp;
        // If this is not the first node then connect it to the rest.
        else
            prev->next = temp;
       
        // Set prev for next insertion
        prev = temp;
 
        // Move first and second pointers to next nodes
        if (first)
            first = first->next;
        if (second)
            second = second->next;
    }
    if (carry > 0)
        temp->next = newNode(carry);
    // return head of the resultant list
    return res;
}
 
Node* reverse(Node* head)
{
    if (head == NULL || head->next == NULL)
        return head;
    // reverse the rest list and put the first element at the end
    Node* rest = reverse(head->next);
    head->next->next = head;
    head->next = NULL;
    // fix the head pointer
    return rest;
}
 
// A utility function to print a linked list
void printList(Node* node)
{
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}
 
/* Driver code */
int main(void)
{
    Node* res = NULL;
    Node* first = NULL;
    Node* second = NULL;
 
    // create first list 7->5->9->4->6
    push(&first, 6);
    push(&first, 4);
    push(&first, 9);
    push(&first, 5);
    push(&first, 7);
    printf("First List is ");
    printList(first);
 
    // create second list 8->4
    push(&second, 4);
    push(&second, 8);
    cout << "Second List is ";
    printList(second);
 
    // reverse both the lists
    first = reverse(first);
    second = reverse(second);
    // Add the two lists
    res = addTwoLists(first, second);
 
    // reverse the res to get the sum
    res = reverse(res);
    cout << "Resultant list is ";
    printList(res);
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)
Output
First List is 7 5 9 4 6 
Second List is 8 4 
Resultant list is 7 6 0 3 0 

Complexity Analysis: 

  • Time Complexity: O(m + n), where m and n are numbers of nodes in first and second lists respectively. 
    The lists need to be traversed only once.
  • Space Complexity: O(m + n). 
    A temporary linked list is needed to store the output number

Method 2(Using STL): Using the stack data structure

Approach :

  • Create 3 stacks namely s1,s2,s3.
  • Fill s1 with Nodes of list1 and fill s2 with nodes of list2.
  • Fill s3 by creating new nodes and setting the data of new nodes to the sum of s1.top(), s2.top() and carry until list1 and list2 are empty .
  • If the sum >9
    • set carry 1
  • else
    • set carry 0
  • Create a Node(say prev) that will contain the head of the sum List.
  • Link all the elements of s3 from top to bottom
  • return prev
     

Code:

// C++ program to add two numbers represented by Linked
// Lists using Stack
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
    int data;
    Node* next;
};
Node* newnode(int data)
{
    Node* x = new Node();
    x->data = data;
    return x;
}
// function that returns the sum of two numbers represented
// by linked lists
Node* addTwoNumbers(Node* l1, Node* l2)
{
    Node* prev = NULL;
    // Create 3 stacks
    stack<Node*> s1, s2, s3;
    // Fill first stack with first List Elements
    while (l1 != NULL) {
        s1.push(l1);
        l1 = l1->next;
    }
    // Fill second stack with second List Elements
    while (l2 != NULL) {
        s2.push(l2);
        l2 = l2->next;
    }
    int carry = 0;
    // Fill the third stack with the sum of first and second
    // stack
    while (!s1.empty() && !s2.empty()) {
        int sum = s1.top()->data + s2.top()->data + carry;
        Node* temp = newnode(sum % 10);
        s3.push(temp);
        if (sum > 9) {
            carry = 1;
        }
        else {
            carry = 0;
        }
        s1.pop();
        s2.pop();
    }
    while (!s1.empty()) {
        int sum = carry + s1.top()->data;
        Node* temp = newnode(sum % 10);
        s3.push(temp);
        if (sum > 9) {
            carry = 1;
        }
        else {
            carry = 0;
        }
        s1.pop();
    }
    while (!s2.empty()) {
        int sum = carry + s2.top()->data;
        Node* temp = newnode(sum % 10);
        s3.push(temp);
        if (sum > 9) {
            carry = 1;
        }
        else {
            carry = 0;
        }
        s2.pop();
    }
    // If carry is still present create a new node with
    // value 1 and push it to the third stack
    if (carry == 1) {
        Node* temp = newnode(1);
        s3.push(temp);
    }
    // Link all the elements inside third stack with each
    // other
    if (!s3.empty())
        prev = s3.top();
    while (!s3.empty()) {
        Node* temp = s3.top();
        s3.pop();
        if (s3.size() == 0) {
            temp->next = NULL;
        }
        else {
            temp->next = s3.top();
        }
    }
    return prev;
}
// utility functions
// Function that displays the List
void Display(Node* head)
{
    if (head == NULL) {
        return;
    }
    while (head->next != NULL) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << head->data << endl;
}
// Function that adds element at the end of the Linked List
void push(Node** head_ref, int d)
{
    Node* new_node = newnode(d);
    new_node->next = NULL;
    if (*head_ref == NULL) {
        new_node->next = *head_ref;
        *head_ref = new_node;
        return;
    }
    Node* last = *head_ref;
    while (last->next != NULL && last != NULL) {
        last = last->next;
    }
    last->next = new_node;
    return;
}
// Driver Program for above Functions
int main()
{
    // Creating two lists
    // first list = 9 -> 5 -> 0
    // second List = 6 -> 7
    Node* first = NULL;
    Node* second = NULL;
    Node* sum = NULL;
    push(&first, 7);
    push(&first, 5);
    push(&first, 9);
    push(&first, 4);
    push(&first, 6);
    push(&second, 8);
    push(&second, 4);
    cout << "First List : ";
    Display(first);
    cout << "Second List : ";
    Display(second);
    sum = addTwoNumbers(first, second);
    cout << "Sum List : ";
    Display(sum);
    return 0;
}
Output
First List : 7 -> 5 -> 9 -> 4 -> 6
Second List : 8 -> 4
Sum List : 7 -> 6 -> 0 -> 3 -> 0

Time Complextiy: O(n)

Here n is length of the larger list 

Auxiliary Space: O(n)

Extra space is used in storing the elements in the stack.

Another Approach with time complexity O(N):

The given approach works as following steps: 

  1. First, we calculate the sizes of both the linked lists, size1 and size2, respectively.
  2. Then we traverse the bigger linked list, if any, and decrement till the size of both become the same.
  3. Now we traverse both linked lists till the end.
  4. Now the backtracking occurs while performing addition.
  5. Finally, the head node is returned to the linked list containing the answer.

#include <iostream>
using namespace std;
 
struct Node {
    int data;
    struct Node* next;
};
 
// recursive function
Node* addition(Node* temp1, Node* temp2, int size1,
               int size2)
{
    // creating a new Node
    Node* newNode
        = (struct Node*)malloc(sizeof(struct Node));
 
    // base case
    if (temp1->next == NULL && temp2->next == NULL) {
        // addition of current nodes which is the last nodes
        // of both linked lists
        newNode->data = (temp1->data + temp2->data);
 
        // set this current node's link null
        newNode->next = NULL;
 
        // return the current node
        return newNode;
    }
 
    // creating a node that contains sum of previously added
    // number
    Node* returnedNode
        = (struct Node*)malloc(sizeof(struct Node));
 
    // if sizes are same then we move in both linked list
    if (size2 == size1) {
        // recursively call the function
        // move ahead in both linked list
        returnedNode = addition(temp1->next, temp2->next,
                                size1 - 1, size2 - 1);
 
        // add the current nodes and append the carry
        newNode->data = (temp1->data + temp2->data)
                        + ((returnedNode->data) / 10);
    }
    // or else we just move in big linked list
    else {
        // recursively call the function
        // move ahead in big linked list
        returnedNode = addition(temp1, temp2->next, size1,
                                size2 - 1);
 
        // add the current node and carry
        newNode->data
            = (temp2->data) + ((returnedNode->data) / 10);
    }
 
    // this node contains previously added numbers
    // so we need to set only rightmost digit of it
    returnedNode->data = (returnedNode->data) % 10;
 
    // set the returned node to the current node
    newNode->next = returnedNode;
 
    // return the current node
    return newNode;
}
 
// Function to add two numbers represented by nexted list.
struct Node* addTwoLists(struct Node* head1,
                         struct Node* head2)
{
    struct Node *temp1, *temp2, *ans = NULL;
 
    temp1 = head1;
    temp2 = head2;
 
    int size1 = 0, size2 = 0;
 
    // calculating the size of first linked list
    while (temp1 != NULL) {
        temp1 = temp1->next;
        size1++;
    }
    // calculating the size of second linked list
    while (temp2 != NULL) {
        temp2 = temp2->next;
        size2++;
    }
 
    Node* returnedNode
        = (struct Node*)malloc(sizeof(struct Node));
 
    // traverse the bigger linked list
    if (size2 > size1) {
        returnedNode = addition(head1, head2, size1, size2);
    }
    else {
        returnedNode = addition(head2, head1, size2, size1);
    }
 
    // creating new node if head node is >10
    if (returnedNode->data >= 10) {
        ans = (struct Node*)malloc(sizeof(struct Node));
        ans->data = (returnedNode->data) / 10;
        returnedNode->data = returnedNode->data % 10;
        ans->next = returnedNode;
    }
    else
        ans = returnedNode;
 
    // return the head node of linked list that contains
    // answer
    return ans;
}
 
void Display(Node* head)
{
    if (head == NULL) {
        return;
    }
    while (head->next != NULL) {
        cout << head->data << " -> ";
        head = head->next;
    }
    cout << head->data << endl;
}
// Function that adds element at the end of the Linked List
void push(Node** head_ref, int d)
{
    Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = d;
    new_node->next = NULL;
    if (*head_ref == NULL) {
        new_node->next = *head_ref;
        *head_ref = new_node;
        return;
    }
    Node* last = *head_ref;
    while (last->next != NULL && last != NULL) {
        last = last->next;
    }
    last->next = new_node;
    return;
}
// Driver Program for above Functions
int main()
{
    // Creating two lists
    Node* first = NULL;
    Node* second = NULL;
    Node* sum = NULL;
    push(&first, 7);
    push(&first, 5);
    push(&first, 9);
    push(&first, 4);
    push(&first, 6);
    push(&second, 8);
    push(&second, 4);
    cout << "First List : ";
    Display(first);
    cout << "Second List : ";
    Display(second);
    sum = addTwoLists(first, second);
    cout << "Sum List : ";
    Display(sum);
    return 0;
}
 
// This code is contributed by Dharmik Parmar
Output
First List : 7 -> 5 -> 9 -> 4 -> 6
Second List : 8 -> 4
Sum List : 7 -> 6 -> 0 -> 3 -> 0

Related Article: Add two numbers represented by linked lists | Set 2

Please write comments if you find the above codes/algorithms incorrect, or find other ways to solve the same problem.
 

Another Approach with easy to understand code (without appending zeros)- 

In this approach we simulate how in reality we add two numbers. In the code we have taken 9->8->7 and 1->2->3 as two numbers to add. What we do is reverse these two lists to get 7->8->9 and 3->2->1 and start from the head of the lists to add numbers of individual nodes like we would in practice if we add two numbers.

For example,  first we add 7 and 3 to get 10, which means carry = 1 and value of new node will be 0. Now we continue this till the end of the list.

Steps- 

  1. Reverse the two number lists.
  2. Simulate addition on nodes one by one. Append each node before the already calculated sum nodes.( You will better understand this step in code)
  3. In the end we will get the final answer and we can return the head node.

// C++ Code to add two nodes by reversing the two lists
 
#include <bits/stdc++.h>
using namespace std;
 
/* Linked list Node */
struct Node {
    int data;
    struct Node* next;
};
 
Node* newNode(int data)
{
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}
 
/* Function to insert a node at the
beginning of the Singly Linked List */
void push(Node** head_ref, int new_data)
{
    /* allocate node */
    Node* new_node = newNode(new_data);
    /* link the old list off the new node */
    new_node->next = (*head_ref);
    /* move the head to point to the new node */
    (*head_ref) = new_node;
}
 
void printList(Node* n)
{
    while (n) {
        cout << n->data << " ";
        n = n->next;
    }
    cout << endl;
}
 
struct Node* reverseList(struct Node* list)
{
    Node *prev = NULL, *cur = list, *next = NULL;
    while (cur != NULL) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}
 
//----------------------------------------------------------------------------
 
Node* addTwoLists(Node* first, Node* second)
{
    // code here
    first = reverseList(first);
    second = reverseList(second);
 
    int carry = 0;
    Node *head = NULL, *prev = NULL;
    Node* sum = NULL;
    // if any one of these is left we are stil left with addition
    while (first != NULL or second != NULL or carry == 1)
    {
        int newVal = carry;
        if (first)
            newVal += first->data;
        if (second)
            newVal += second->data;
        // to be used in the next node calculation
        carry = newVal / 10;
        newVal = newVal % 10;
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->data = newVal;
        // appending in the beginning of the final ans list,
        // this way we do not have to reverse in the end
        newNode->next = sum;
        sum = newNode;
        // initialising nodes for next iteration
 
        if (first)
            first = first->next;
        if (second)
            second = second->next;
    }
 
    return sum;
}
 
//----------------------------------------------------------------------------
 
// { Driver Code Starts.
 
int main()
{
    Node* first = NULL;
    Node* second = NULL;
 
    push(&first, 9);
    push(&first, 8);
    push(&first, 7);
 
    push(&second, 1);
    push(&second, 2);
    push(&second, 3);
 
    Node* ans = addTwoLists(first, second);
 
    cout << "Sum is : ";
    printList(ans);
 
    return 0;
}
 
// This code is contributed by Aditya Kumar (adityakumar129)
Output
Sum is : 1 1 1 0 

Complexity Analysis:

Time Complexity: O(max(m,n)), where m and n are numbers of nodes in first and second lists respectively. 
The lists need to be traversed only once.
Space Complexity: O(1)
As constant extra space is used.

  Write a Program to Find the Maximum Depth or Height of a Tree Difficulty Level : Easy Last Updated : 21 Jul, 2022 Read Discuss Given ...