September 30, 2024

Add Two Numbers Represented by Linked Lists

Problem Statement

In this problem add two numbers represented by linked lists, You will be given two numbers represented by two separate Linked List, and write a function that returns the sum list.

A sum list is a list that represents the sum of two input numbers (Linked List).

Rules :

In both, the numbers list the digits are stored in a reverse order.
Each of the nodes of the Linked List must contain a single digit.
The two numbers (Linked List) do not contain any leading zero, except the number 0 itself.

Input Format :

Two numbers are represented by two Linked List heads.

Output Format :

Return the sum of the two input numbers which is represented by Linked List in reverse order.

Example

Let’s understand this problem add two numbers represented by linked lists with help of examples.

Example : 1

Input :

l1 = {2, 4, 3}
l2 = {5, 6, 4}

Output :

{7, 0, 8}

Explanation :

Let us now understand the above example in detail.

In the above example, we are taking two Linked List as input, and we are considering them as numbers.
Since it is given that the Linked List contains digits of the number in reverse order. The list l1 which consists of {2, 4, 3} nodes will be represented as the number 342, and the list l2 which consists of {5, 6, 4} nodes will be represented as the number 465.
So, we need to return a resultant Linked List in the reverse order that should represent the sum of the above two Linked Lists, i.e., $342 + 465 = 807$.
So, in the above example we will return the Linked List form of the number 807 in reverse order, that is, {7, 0, 8}.

Example of addition of numbers represented by linked lists

Example : 2

Input :

l1 = {5, 1}
l2 = {7, 9, 3}

Output :

{2, 1, 4}

Explanation :

Let us now understand the above example in detail.

In the above example, we are taking two Linked List as input, and we are considering them as numbers.
Since it is given that the Linked List contains digits of the number in reverse order. The list l1 which consists of {5, 1} nodes will be represented as the number 15, and the list l2 which consists of {7, 9, 3} nodes will be represented as the number 397
So, we need to return a resultant Linked List in the reverse order that should represent the sum of the above two Linked Lists, i.e., $15 + 397 = 412$.
So, in the above example we will return the Linked List form of the number 412 in reverse order, that is, {2, 1, 4}.

Input :

Input linked lists

Output :

Resultant linked lists

Constraints

The number of nodes in each linked list is in the range [1, 100].
$0 <=$ Node.val $<= 9$
It is guaranteed that the list represents a number that does not have leading zeros.

Approach : 1

Let us begin with the brute force approach of adding two numbers represented by linked lists. We are going to use some extra space, and it is slow but should be mentioned during the interview.

Intuition :

In the brute force approach add two numbers represented by linked lists. To add two numbers, the simplest thing we can do is to reverse the two linked lists (as they contain the digits in reverse order). Then convert the two numbers in linked lists into integers. Add these integers and convert the sum back to a linked list such that it contains digits in reverse order.

In this approach, we will need to implement the following functions :

To reverse both the Linked List.
Covert both the Linked List into integer.
Find the sum of both integers.
Reverse the resultant integer and then convert it into a Linked List.

Algorithm :

Here is the brute force algorithm for this particular problem add two numbers represented by linked lists :

Firstly, reverse both the given Linked List l1 and l2.
Then, convert the numbers represented by both the linked list into integers n1 and n2.
Then, add both the numbers as $sum = n1 + n2$.
Then, convert the above-calculated sum back to a Linked List using the toLinkedList() function which will one by one take the digits from the end of the number passed and create a linked list using them. And finally, return it. Note, in the toLinkedList() function the number’s digit will be added in reverse order. ans = to_linkedlist(sum).
Return the resultant linked list ‘ans’ containing the sum.
Note : This approach will not work for huge input numbers represented by Linked List, which is out of the range of integer, and it will throw an overflow error.

Code

Now, let us see the code of adding two numbers represented by linked lists problem in different programming languages.

Code in JAVA :

// Java program to add two numbers
// represented by linked list

import java.util.*;

// Node Class
class Node{
	int data;
	Node next;
	Node(int data, Node next){
		this.data = data;
		this.next = next;
	}
}

// Public class
public class MyClass{

    // convertList method to
    // convert Integer to List
    public static Node convertList(int num){
        Node l = null;
        while(num != 0){
			l = new Node(num%10, l);
			num = num/10;
		}
		return l;
    }

    // toInteger method to
    // convert List to Integer
	public static int toInteger(Node l){
		Node curr = l;
		int ans = 0;
		while(curr != null){
			ans = ans*10 + curr.data;
			curr = curr.next;
		}
		return ans;
	}

	// reverse method to reverse
	// the Linked List
	public static Node reverse(Node head){
		Node prev = head;
		Node curr = head.next;
		while(curr != null){
			Node next = curr.next;
			curr.next = prev;
			prev = curr;
			curr = next;
		}
		head.next = null;
		head = prev;
		return head;
	}

	// addList to add the content
	// of the Linked List
	public static Node addList(Node l1, Node l2){
		l1 = reverse(l1);
		l2 = reverse(l2);
		int num1 = toInteger(l1);
		int num2 = toInteger(l2);
		int sum = num1 + num2;
		Node l3 = convertList(sum);
		l3 = reverse(l3);
		return l3;
	}

	// printList to print the content
	// of the Linked List
	public static void printList(Node ans){
	    Node curr = ans;
	    while(curr != null){
	        System.out.print(curr.data+" ");
	        curr = curr.next;
	    }
	}

	// main method
	public static void main(String[] args){
		int x = 243;
		int y = 564;
		Node l1 = convertList(x);
		Node l2 = convertList(y);
		Node ans = addList(l1, l2);
		printList(ans);
	}
}

Output :

7 0 8

Code in C++ :

#include<bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node* next;

    Node(int value){
        val = value;
        next = NULL;
    }
};

void push_front(Node** head, int new_val){
    Node* new_node = new Node(new_val);
    new_node->next = *head;
    *head = new_node;
}

void printList(Node* head){
    Node* i = head;
    while(i){
        cout<<i->val<<" ";
        i = i->next;
    }
    cout<<"\n";
}

// function to reverse a linked list
Node* reverse_it(Node* head){
    Node *prev = NULL;
     Node *curr = head, *next;
    while(curr!=NULL){
        next = curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }
    return prev;
}

// function to convert a linked list to an integer
int to_integer(Node* head){
    int num = 0;
    Node* curr = head;
    while(curr){
        int digit = curr->val;
        num = num*10 + digit;
        curr = curr->next;
    }
    return num;
}

// function to convert a number to a linked list
// containing digits in reverse order
Node* to_linkedlist(int x){
    Node* head = new Node(0);
    if(x==0) return head;


    Node* curr = head;
    while(x){
        int d = x%10;
        x /= 10;
        curr->next = new Node(d);
        curr = curr->next;
    }
    return head->next;
}

// function to add 2 numbers given as linked lists
Node* add_list(Node* l1, Node* l2){
    // reversing the 2 linked lists
    l1 = reverse_it(l1);
    l2 = reverse_it(l2);

    // converting them into integers
    int num1 = to_integer(l1);
    int num2 = to_integer(l2);

    int sum = num1 + num2;
    // converting the sum back to
    // a linked list
    Node* ans = to_linkedlist(sum);

    return ans;
}


int main(){
    Node* l1 = NULL;

    push_front(&l1, 2);
    push_front(&l1, 4);
    push_front(&l1, 3);

    Node* l2 = NULL;

    push_front(&l2, 5);
    push_front(&l2, 6);
    push_front(&l2, 4);

    // l1-> 2 4 3
    // l2-> 5 6 4

    Node* sum = add_list(l1,l2);

    printList(sum);
    // 7 0 8
}

Output :

7 0 8

Code in Python :

# Node for linked list:

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


class Solution:
    def __init__(self):
        self.head = None
    #Function to add two numbers represented by linked list.
    def addTwoLists(self, l1, l2):
        q1 = []
        q2 = []
        while l1:
            q1.append(l1.data)
            l1 = l1.next
        while l2:
            q2.append(l2.data)
            l2 = l2.next
        q1 = [str(i) for i in q1]
        s1 = int("".join(q1[::-1]))
        q2 = [str(i) for i in q2]
        s2 = int("".join(q2[::-1]))
        s = s1+s2
        s = [i for i in str(s)]
        s = s[::-1]
        head = l = Node(0)
        for i in s:
            l.next = Node(i)
            l = l.next
        return head.next

# Node Class
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Linked List Class
class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    # creates a new node with given value and appends it at the end of the linked list
    def insert(self, val):
        if self.head is None:
            self.head = Node(val)
            self.tail = self.head
        else:
            self.tail.next = Node(val)
            self.tail = self.tail.next

# prints the elements of linked list starting with head
def printList(n):
    while n:
        print(n.data,end=' ')
        n = n.next
    print()

if __name__ == '__main__':

        arr1 = [2,4,3]
        arr2 = [5,6,4]

        LL1 = LinkedList()
        for i in arr1:
            LL1.insert(i)

        LL2 = LinkedList()
        for i in arr2:
            LL2.insert(i)
        obj = Solution()
        res = obj.addTwoLists(LL1.head, LL2.head)
        printList(res)

Output :

7 0 8

Time Complexity

In this approach of adding two numbers represented by linked lists, Firstly, we are reversing both the list l1 and l2, then we are converting them into integers. So overall the time complexity for this code will be $O(n+m)$.

T.C : $O(n+m)$, where $n, m$ are the number of nodes in the linked lists.

Space Complexity

The space complexity for the above implementation will depend upon the number of digits in our final result (after calculating the sum). This is very obvious because, as we are expected to store our final result in a Linked List, for every digit there will be a linked list node. So, for $N$ digits, the total space taken by the linked list will be $O(N)$, assuming, $N$ is the number of digits in our final result sum. Since, we know the final sum will mainly depend upon the maximum number of digits, from each of the numbers provided to us. Hence, we can conclude that our space complexity will depend on $O(max(n,m))$, where $m$ and $n$ are the number of digits in num1 and num2 respectively.

Approach : 2

The above approach of adding two numbers represented by the problem of the linked list is a brute force approach, and it will work only for input numbers that are small enough to belong in the range of integer data. What if the number of digits in the input number is huge let’s say 30 ? For this type of input, the above approach will not work and we need to improve upon it.

Let us now see a much better and optimal approach of adding two numbers represented by the problem of the linked list, which will even work perfectly for the input number’s digit out of range of integer datatype.

Intuition :

Here in this approach of adding two numbers represented by the problem of the linked list, we are not going to convert the Linked List into an integer and then calculate the sum, but we will do it in place with the help of the two-pointer method. We can simply iterate both the linked lists and keep on calculating the sum of values in nodes. Along with that, we will also maintain a carry in which we will store the first digit of the sum that comes out to be two-digit in any node. While taking the sums we will add the previous carry to it and add a new node to the result containing the last digit in the sum and update the carry for the next iteration.

We can simply iterate the 2 linked lists and take the sum of the values in nodes along with maintaining a carry. While taking sums add the previous carry to it and add a new node to the result containing the last digit in the sum and update the carry for the next iteration.

Algorithm :

We are going to use the two-pointer method to solve this problem.
Firstly, we will use 2 pointers to store the head of each linked list and initialize a carry variable as 0. Note, in the case of Java there is no concept of pointers, so in Java, we are going to use 2 iterators.
Then, we declare a pointer (iterator in case of Java) to the node to store our resultant answer represented by Linked List.
We will iterate through both the linked list and keep on adding the digits pointed by the pointers. The moment we have reached the end of any one of the linked lists and we have no further nodes of that linked list, we will consider its value as 0 while iterating for the other linked list which is still having the nodes, and keep calculating the sum.
We will add a new node with $(sum + carry)\%10$ as value to our answer and update carry as $(sum + carry) / 10$.
We will keep on repeating steps 3 and 4 until we reach the end of both of the linked lists. If one of the Linked List is smaller in size than the other one, it gets ended before the other Linked List. In that case, we will continue the iteration, just in the place of the smaller Linked List’s value, we will add 0 until the other Linked List also gets over.
After traversing both the linked lists, if the carry is greater than 0 $(carry > 0)$ then add this carry to our answer as a new node.

Code

Now, let us see the code of adding two numbers represented by linked lists problem in different programming languages.

Code in JAVA :

// Java program to add two numbers
// represented by linked list

import java.util.*;

// Node Class
class Node{
	int data;
	Node next;
	Node(int data){
	    this.data = data;
	}
	Node(int data, Node next){
		this.data = data;
		this.next = next;
	}
}

// Public class
public class AddTwoList{

    // addList to add the content
	// of the Linked List using
	// two pointer method
	public static Node addList(Node l1, Node l2){
		Node p1 = l1;
		Node p2 = l2;
		Node ans = new Node(0);
		Node curr = ans;
		int carry = 0;
		while(p1 != null || p2 != null){
		    int sum = ((p1 != null)? p1.data : 0) + ((p2 != null)? p2.data : 0) + carry;
		    carry = sum/10;
		    int mod = sum%10;
		    curr.next = new Node(mod);
		    curr = curr.next;
		    p1 = p1.next;
		    p2 = p2.next;
		}
		if(carry > 0){
		    curr.next = new Node(carry);
		}
		return ans.next;
	}

	// printList to print the content
	// of the Linked List
	public static void printList(Node ans){
	    Node curr = ans;
	    while(curr != null){
	        System.out.print(curr.data+" ");
	        curr = curr.next;
	    }
	}

	// main method
	public static void main(String[] args){
		int x = 243;
		int y = 564;
		Node l1 = null;
		while(x != 0){
			l1 = new Node(x%10, l1);
			x = x/10;
		}
		Node l2 = null;
		while(y != 0){
			l2 = new Node(y%10, l2);
			y = y/10;
		}
		Node ans = addList(l1, l2);
		printList(ans);
	}
}

Output :

7 0 8

Code in C++ :

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int val;
    Node* next;

    Node(int value){
        val = value;
        next = NULL;
    }
};

void push_front(Node** head, int new_val){
    Node* new_node = new Node(new_val);
    new_node->next = *head;
    *head = new_node;
}

void printList(Node* head){
    Node* i = head;
    while(i){
        cout<<i->val<<" ";
        i = i->next;
    }
    cout<<"\n";
}

// function to add 2 numbers given as linked lists
Node* add(Node* l1, Node* l2){
    Node* ans = new Node(0);
    Node* curr = ans;
    int carry = 0;
    while(l1 || l2){
        int sum = 0;
        if(l1) sum += l1->val;
        if(l2) sum += l2->val;
        sum += carry;

        curr->next = new Node(sum%10);
        curr = curr->next;

        carry = sum/10;

        if(l1) l1 = l1->next;
        if(l2) l2 = l2->next;
    }

    if(carry){
        curr->next = new Node(carry);
    }
    ans = ans->next;
    return ans;
}

int main(){
    Node* l1 = NULL;

    push_front(&l1, 2);
    push_front(&l1, 4);
    push_front(&l1, 3);

    Node* l2 = NULL;

    push_front(&l2, 5);
    push_front(&l2, 6);
    push_front(&l2, 4);

    // l1-> 2 4 3
    // l2-> 5 6 4

    Node* sum = add(l1,l2);

    printList(sum);
    // 7 0 8     = 412
}

Output :

7 0 8

Code in python :

# A Linked List Node
class Node:
    def __init__(self, data=None, next=None):
        self.data = data
        self.next = next


# Function to print a given linked list
def printList(head):

    ptr = head
    while ptr:
        print(ptr.data, end=' ')
        ptr = ptr.next
    # print('None')


# Iterate through the list and move/insert each node
# in front of the out list like `push()` of the node
def reverse(head):

    out = None
    current = head

    # traverse the list
    while current:
        # tricky: note the next node
        next = current.next

        # move the current node onto the out
        current.next = out
        out = current

        # process next node
        current = next

    # fix head
    return out


# Function to add two lists, `X` and `Y`
def append(X, Y):

    head = None

    # stores the last seen node
    prev = None

    # initialize carry with 0
    carry = 0

    # run till both lists are empty
    while X or Y:

        # sum is X's data + Y's data + carry (if any)
        total = 0
        if X:
            total += X.data
        if Y:
            total += Y.data

        total += carry

        # if the sum of a 2–digit number, reduce it and update carry
        carry = total // 10
        total = total % 10

        # create a new node with the calculated sum
        node = Node(total)

        # if the output list is empty
        if head is None:
            # update `prev` and `head` to point to the new node
            prev = node
            head = node
        else:
            # add the new node to the output list
            prev.next = node

            # update the previous node to point to the new node
            prev = node

        # advance `X` and `Y` for the next iteration of the loop
        X = X.next if X else X
        Y = Y.next if Y else Y

    if carry:
        prev.next = Node(carry, prev.next)

    return head


# Function to add two lists, `X` and `Y`
def addLists(X, Y):

    # reverse `X` and `Y` to access elements from the end


    return append(X, Y)


if __name__ == '__main__':

    x = 243
    y = 564

    # construct list `X` (2 —> 4 —> 3) from number `x`
    X = None
    while x:
        X = Node(x % 10, X)
        x = x // 10

    # construct list `Y` (5 —> 6 —> 4) from number `y`
    Y = None
    while y:
        Y = Node(y % 10, Y)
        y = y // 10

    printList(addLists(X, Y))

Output :

7 0 8

Time Complexity

In this approach add two numbers represented by the problem of the linked list, as we are traversing both the list l1 and l2, and we are calculating the sum of the numbers. So the overall time complexity for this code will be $O(n+m)$.

T.C : $O(n+m)$, where $n, m$ are the number of nodes in the linked lists.

Space Complexity

The overall space complexity of this approach will depend on the number of digits in the sum, which will depend on the number having more digits.

$O(max(n,m))$, as the number of digits in the sum will depend on the number having more digits.

Note : To avoid the use of extra space we can store the sum in one of the linked lists itself or modify one of the Linked List itself.

Approach : 3

Now let us see another approach of how we can solve this add two numbers represented by linked lists problem with the help of a data structure stack, and how we can add the numbers of both the Linked List using a stack. This approach is not that efficient, as here we have to make sure that the size of the list should not exceed the limit of the stack, or it will throw an error of overflow.

Intuition :

In this approach we are going to use three stacks, out of which in two stacks s1, s2 we are going to store the nodes of both the Linked List and in the third stack s3 we will store the sum of the numbers of both the list inside the stacks s1, s2.

Algorithm :

Firstly, we are going to create 3 stacks named s1, s2, and s3.
Then, we will fill the stack s1 with Nodes of Linked List l1 and the stack s2 with Nodes of Linked List l2.
We will initialize a carry variable in which we will store the first digit of the sum that comes out to be two-digit in any node. If the sum is greater than 9 we will set the carry as 1 else we will set the carry as 0.
Now, we will start filling the stack s3 by creating new nodes and storing the data of that new node to the sum of s1.top(), and s2.top() and carry until both the list l1 and l2 are empty. We will create a Node (say prev) that will contain the head of the sum List inside the stack s3.
Now, connect all the elements of s3 from top to bottom and then reverse the list as return prev.

Code

Now, let us see the code of adding two numbers represented by linked lists problem in different programming languages.

Code in JAVA :

// Java program to add two numbers
// represented by linked list

import java.util.*;

// Node Class
class Node{
	int data;
	Node next;
	Node(int data){
	    this.data = data;
	}
	Node(int data, Node next){
		this.data = data;
		this.next = next;
	}
}

public class AddTwoList{

    // reverse method to reverse
	// the Linked List
	public static Node reverse(Node head){
		Node prev = head;
		Node curr = head.next;
		while(curr != null){
			Node next = curr.next;
			curr.next = prev;
			prev = curr;
			curr = next;
		}
		head.next = null;
		head = prev;
		return head;
	}

    // addList to add the content
	// of the Linked List using
	// stack method
	public static Node addList(Node l1, Node l2){
	    Stack<Node> s1 = new Stack<>();
	    Stack<Node> s2 = new Stack<>();
	    Stack<Node> s3 = new Stack<>();


		Node p1 = l1;
		Node p2 = l2;

		// adding the nodes of the list
		// l1 inside stack s1
		while(p1 != null){
		    s1.push(p1);
		    p1 = p1.next;
		}

		// adding the nodes of the list
		// l2 inside stack s2
		while(p2 != null){
		    s2.push(p2);
		    p2 = p2.next;
		}


		int carry = 0;
		while(!s1.isEmpty() || !s2.isEmpty()){
		    int sum = ((!s1.isEmpty())? s1.pop().data : 0) + ((!s2.isEmpty())? s2.pop().data : 0) + carry;
		    carry = sum/10;
		    int mod = sum%10;
		    Node node = new Node(mod);
		    s3.push(node);
		}
		if(carry > 0){
		    s3.push(new Node(carry));
		}

		Node ans = new Node(0);
		Node curr = ans;
		while(!s3.isEmpty()){
		    curr.next = s3.pop();
		    curr = curr.next;
		}

		ans = reverse(ans.next);
		return ans;
	}

	// printList to print the content
	// of the Linked List
	public static void printList(Node ans){
	    Node curr = ans;
	    while(curr != null){
	        System.out.print(curr.data+" ");
	        curr = curr.next;
	    }
	}

	// main method
	public static void main(String[] args){
		int x = 243;
		int y = 564;
		Node l1 = null;
		while(x != 0){
			l1 = new Node(x%10, l1);
			x = x/10;
		}
		Node l2 = null;
		while(y != 0){
			l2 = new Node(y%10, l2);
			y = y/10;
		}
		Node ans = addList(l1, l2);
		printList(ans);
	}
}

Output :

7 0 8

Code in C++

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

struct Node {
    int val;
    Node* next;

    Node(int value){
        val = value;
        next = NULL;
    }
};

void push_front(Node** head, int new_val){
    Node* new_node = new Node(new_val);
    new_node->next = *head;
    *head = new_node;
}

void printList(Node* head){
    Node* i = head;
    while(i){
        cout<<i->val<<" ";
        i = i->next;
    }
    cout<<"\n";
}

// function to add 2 numbers given as linked lists
Node* add(Node* l1, Node* l2){
   stack<int>s1;
        stack<int>s2;
        int size1=0;
        int size2=0;
        while(l1!=NULL)
        {
            s1.push(l1->val);
            l1=l1->next;
            size1++;
        }
        while(l2!=NULL)
        {
            s2.push(l2->val);
            l2=l2->next;
            size2++;
        }
        unsigned long long num1=0;
        unsigned long long num2=0;
        while(!s1.empty() && size1!=0)
        {
            num1=num1+(s1.top()*pow(10,size1-1));
            s1.pop();
            size1--;
        }
        while(!s2.empty() &&size2!=0)
        {
            num2=num2+(s2.top()*pow(10,size2-1));
            s2.pop();
            size2--;
        }
        unsigned long long result=num1+num2;
        vector<int>ans;
        if(result==0)
            ans.push_back(0);
        while(result>0)
        {
            unsigned long long k=result%10;
            ans.push_back(k);
            result=result/10;
        }
        Node* head=new Node(ans[0]);
        Node* curr;
        curr=head;
        for(int i=1;i<ans.size();i++)
        {
            Node* curr1=new Node(ans[i]);
            curr->next=curr1;
            curr=curr->next;
        }
        return head;
}

int main(){
    Node* l1 = NULL;

    push_front(&l1, 2);
    push_front(&l1, 4);
    push_front(&l1, 3);

    Node* l2 = NULL;

    push_front(&l2, 5);
    push_front(&l2, 6);
    push_front(&l2, 4);

    // l1-> 2 4 3
    // l2-> 5 6 4

    Node* sum = add(l1,l2);

    printList(sum);
    // 7 0 8     = 412
}

Output :

7 0 8

Code in python :

# Node for linked list:

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


class Solution:
    def __init__(self):
        self.head = None
    #Function to add two numbers represented by linked list.
    def addTwoLists(self, l1, l2):
        stack = []
        prev = None
        temp = None
        carry = 0
        while l1 is None or l2 is None:
            dFirst = 0 if l1 is None else l1.data
            dSecond = 0 if l2 is None else l2.data
            Sum =  carry + dFirst + dSecond
            carry = 1 if Sum>=10 else 0
            Sum = Sum if Sum<10 else Sum % 10
            stack.append(Sum)

            # update the l1
            if l1 is not None:
                l1 = l1.next
            # update the l2
            if l2 is not None:
                l2 = l2.next
        if carry > 0:
            stack.append(carry)
        for i in range(len(stack)-1, -1, -1):
            new_node = Node(stack[i])
            if self.head is None:
                self.head = new_node
            else:
                new_node.next = self.head
            self.head = new_node
        return self.head

# Node Class
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

# Linked List Class
class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    # creates a new node with given value and appends it at the end of the linked list
    def insert(self, val):
        if self.head is None:
            self.head = Node(val)
            self.tail = self.head
        else:
            self.tail.next = Node(val)
            self.tail = self.tail.next

# prints the elements of linked list starting with head
def printList(n):
    while n:
        print(n.data,end=' ')
        n = n.next
    print()

if __name__ == '__main__':

        arr1 = [2,4,3]
        arr2 = [5,6,4]

        LL1 = LinkedList()
        for i in arr1:
            LL1.insert(i)

        LL2 = LinkedList()
        for i in arr2:
            LL2.insert(i)
        obj = Solution()
        res = obj.addTwoLists(LL1.head, LL2.head)
        printList(res)

Output :

7 0 8

Time Complexity

In this approach of adding two numbers represented by the problem of the linked list, as we are traversing both the list l1 and l2, we are storing them in stacks. So the overall time complexity for this code will be $O(n+m)$.

Time Complexity : $O(n+m)$, where $n, m$ are the number of nodes in the linked lists.

Space Complexity

In the above implementation, we are storing the nodes of both the Linked List inside two different stacks, so it will occupy $O(n) + O(m)$ space, where n and m are the size of both the Linked list. Now, we are storing their sum inside another stack which will again occupy a space of $O(max(n, m))$ as discussed above, the space of the sum will depend upon the input number of more digits. So the overall space will be $O(n + m + max(n,m))$.

$O(n) + O(m) + O(max(n,m))$. However, this approach is not much efficient as we are using a lot of space here.

Conclusion

In this article, we learned about the problem, then added two numbers represented by linked lists.

Let us recap the points we discussed throughout the article :

Basically, in this problem add two numbers represented by Linked List, you will be given two numbers represented by two Linked List, we have to write a function that returns the sum of both lists number-wise.
At first, we applied the brute force approach for this problem add two numbers represented by linked lists. In which we reverse the two linked lists (as they contain the digits in reverse order). Then convert the two numbers in linked lists into integers. Add these integers and convert the sum back to a linked list such that it contains digits in reverse order.
Then, we applied the optimal approach for this problem add two numbers represented by linked lists. In which we will use the Two Pointer technique.
In this Two Pointer approach, We can simply iterate both the linked lists and keep on calculating the sum of values in nodes. Along with that, we will also maintain a carry in which we will store the first digit of the sum that comes out to be two-digit in any node. While taking the sums we will add the previous carry to it and add a new node to the result containing the last digit in the sum and update the carry for the next iteration.
Using the Two Pointer approach, the code will even work perfectly for the input number’s digit out of range of integer datatype.
Then, we solved this problem using another approach for this problem adding two numbers represented by linked lists, that is, by using stack data structure.
In this approach we will use three stacks, out of which in two stacks s1, s2 we are going to store the nodes of both the Linked List and in the third stack s3 we will store the sum of the numbers of both the list inside the stacks s1, s2.

Frequently Asked Questions

Q. How Should We Approach a Problem Like this ?

A. Firstly, you need to understand the problem properly. Then think of an algorithm for this problem. Then begin with the Brute Force approach. Later, try to optimize your code.

Learn More

Find the Middle Element in Linked List

Author

Deepak Pandey

View all posts

Add Two Numbers Represented by Linked Lists

Problem Statement

Example

Example : 1

Example : 2

Constraints

Approach : 1

Code

Time Complexity

Space Complexity

Approach : 2

Code

Time Complexity

Space Complexity

Approach : 3

Code

Time Complexity

Space Complexity

Conclusion

Frequently Asked Questions

Learn More

Author

Latest articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?

Add Two Numbers Represented by Linked Lists

Problem Statement

Example

Example : 1

Example : 2

Constraints

Approach : 1

Code

Time Complexity

Space Complexity

Approach : 2

Code

Time Complexity

Space Complexity

Approach : 3

Code

Time Complexity

Space Complexity

Conclusion

Frequently Asked Questions

Learn More

Author

Latest articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?

Featured articles

Largest Number Formed from an Array

Fundamentals of Enhanced Interior Gateway Routing Protocol

What is Network Hub?