Add two numbers represented by linked lists

Add two numbers represented by linked lists

Given two linked lists, where linked list represents a big number and each node of linked list contains one digit of the number. Problem is to add two numbers represented by linked lists. The result should be stored in a third linked list. It should be noted that the head node contains the most significant digit of the numbers.

For example. let’s say we have been given two numbers: 12563 and 56743 and we have to add them. Two linked lists which will represent these numbers are as shown below.

add two numbers represented by linked lists
add two numbers represented by linked lists

Result of adding these two linked list would be:

result of adding two numbers represented by linked lists

Adding two linked lists: thoughts

This problem is very easy to solve if the order of the digits stored in the linked list is reversed. Look at the code given at leetcode.

 public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
       int carry =0;
 
        ListNode newHead = new ListNode(0);
        ListNode p1 = l1, p2 = l2, p3=newHead;
 
        while(p1 != null || p2 != null){
            if(p1 != null){
                carry += p1.val;
                p1 = p1.next;
            }
 
            if(p2 != null){
                carry += p2.val;
                p2 = p2.next;
            }
 
            p3.next = new ListNode(carry%10);
            p3 = p3.next;
            carry /= 10;
        }
 
        if(carry==1) 
            p3.next=new ListNode(1);
 
        return newHead.next;
    }

However, linked lists are not stored in reversed order and basic mathematics tells us that addition starts from the least significant digit. To access least significant digit of the numbers, we will visit the last nodes of both the lists and add them up, create a new node to store the result, take care of the “carry” if any.

Next, we go to the second to last node and do the same. Link the result node to the result node which was created when we added the last nodes.

This will continue  backwards till we reach head of one the list. Once, we reach head of a linked list, we just add all the nodes of the remaining list to the result.

It is clear that we go to the end of the lists and move back one node at a time. Actually, this is a reverse traversal of a linked list, which can easily be done with recursion, function call stack will automatically store previous nodes. However, we need to take into account the difference in the number of digits in two number and hence the difference in length of the two lists.

So before starting recursion, calculate the size difference and move the longer list pointer to appropriate place so that we reach the last node of both lists at the same time.

Another thing is to take care of is carry. If two digits add more than 10, forward the carry to the next node and add it to it. If most significant digit addition results in a carry, create an extra node to store carry.

Add two numbers represented by linked lists: implementation

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

typedef struct node{
	int data;
	struct node *next;
} Node;


int length( Node * head ){
	int len = 0;
	Node * current  = head;
	while(current){
		len++;
		current = current->next;
	}
	return len;
}

Node * createNode(int value){
	
	Node * newNode = (Node *)malloc(sizeof(Node));
	newNode->data = value;
	newNode->next = NULL;
	
	return newNode;

}
/* Addition of a node to linked list */
void push(Node **head, int value){
	
	Node *newNode = createNode (value);
	if(!(*head) ){
		*head = newNode;
	}
	else{
		newNode->next = (*head);
		*head = newNode;
	}
}
/* This function is actually helper function 
	which does all house keeping like calculating 
	lengths of lists,calling recursive implementation,
	creating extra node for carry in MSD,
	and adding any remaining nodes left in longer list. */

/* result is pointer to pointer to the head of resulting node */ 
void addTwoNumbers(Node *L1, Node *L2, int *carry, Node  **result)
{
	int len1 = length( L1 );
	int len2 = length( L2 );
	int diff = 0;
	
	if(len1 < len2){
		Node * current = L1;
		L1 = L2;
		L2 = current;
    }
    diff = abs(len1-len2);
    Node * current = L1;
    
    while(diff--)
    	current = current->next;
    	
    /* Call the recursive implementation */
    addListRecursively(current, L2, carry, result);
    
    diff = abs(len1-len2);
    
    /* Add remaining nodes in longer list */
    addRemainingDigits(L1, carry, result, diff);
    
    if(*carry){
    	push(result, *carry);
    }
    return;
}
void addListRecursively(Node *L1, Node *L2, 
						int *carry, Node **result){

        int sum;
        if(!L1)
            return;

        addListRecursively(L1->next, L2->next, carry, result);

        /*We have reached the last node of both lists, add them */
        sum = L1->data + L2->data + (*carry);
       
        int value = sum%10;
		*carry = sum/10;
        push(result, value);
       
        return;
}
void addRemainingDigits(Node *L1, int *carry,
						Node **result, int diff){
	int sum =0;
	
	if(!L1 || !diff)
		return;
	addRemainingDigits(L1->next, carry, result, diff-1);
	
	sum = L1->data + (*carry);
	int value = sum%10;
	*carry = sum/10;
    
    push(result, value);
    
    return;
}

void printList( Node * head ){
	Node * current = head;
	while(current){
		printf("%d ->", current->data);
		current = current->next;
	}
	printf("NULL");
}
/* Driver program to run above code */
int main(){
        Node * L1 = NULL;
        Node * L2 = NULL;
        Node * result = NULL;
        int carry = 0 ;
        /* creating list 1 */
        push(&L1,3);
        push(&L1,4);
        push(&L1,6);
        push(&L1,7);
        /* creating list 2 */
        push(&L2,8);
        push(&L2,9);
        push(&L2,7);
      
        printList(L1);
        printf("\n");
        printList(L2);
        
        addTwoNumbers(L1,L2, &carry, &result);
        printf("\n");
        printList(result);
        return 0;
}

Since we traverse the number of nodes in the long list, the complexity of the algorithm would be O(n), where n is the number of nodes in the long list. Also, we need n extra nodes to store the result. Hence space complexity to add two numbers represented by linked lists is O(n).

Please share if there something wrong or missing. If you are preparing for an interview, please signup for free interview preparation kit.