Add two numbers represented by linked lists

Add two numbers represented by linked lists

Given two linked lists, each node contains one digit of numbers, add two numbers represented by linked lists. Result should be third linked list. It should be noted that head nodes of linked lists contain most significant digit of numbers. For example, two numbers 12345 and 56789 are represented in form of linked list as follows:

First list : 1->2->3->4->5->NULL
Second list : 5->6->7->8->9->NULL

Result of add two numbers represented by linked lists above should be:

6->9->1->3->4->NULL

Another case:

First list : 5->8->7->NULL
Second list: 6->5->3->NULL
Resultant list : 1->2->4->0->NULL (notice :new head node is created)

Linked list basics can be read at this post : Linked list in C

Add two numbers represented by linked lists : Algorithm

One way to solve this is to reverse two given linked list, add them up and finally reverse resultant list which will represent result of add two numbers represented by linked lists.

There is another way where linked list are not reversed. Addition of two numbers starts from least significant digit, start from last node of both lists and add them up, create new node to store result. Take care of the carry if sum of two numbers in nodes is more than 10. Put this node as next of node which is generated when second least significant nodes are added and continue till heads of two lists are added.

Here, there is something which is interesting. Once last nodes are added, we are left with task to add two linked list, each one node less. That mean once last nodes of two lists are added, original problem reduces to subproblem which can be solved in exactly same manner. Rings some bell? This is very good case for recursion.

However, we need to take into account the difference in number of digits in two number which will result in different number of nodes in linked list.So before starting recursion, calculate length of two lists and move longer list pointer to appropriate place so  last nodes of both lists are visited at same time.

Second, take care of carry which is generated by adding two numbers. If two numbers add up more than 10, we need to forward carry to next nodes and add carry to them. If most significant digit addition results in carry, create an extra node to store carry.

Third, see that resulting nodes are linked correctly and final list in correct order.

There is no algorithms as such, this problem involves working with recursion on linked lists and pointer handling. So let’s see implementation.

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;
}

Add two numbers represented by linked list : Test cases

1. Two lists are of same length
    L1 = 1->2->3->NULL
    L2 = 4->5->6->NULL
 

2. Two lists of different length
    L1 = 1->2->3->4->NULL
    L2 = 4->5->6->NULL
 

3. One list being NULL
    L1= NULL
    L2 = 4->5->6->NULL
 

4. Both lists are NULL
    L1 = NULL
    L2 = NULL
 

5. Carry generated
    L1 = 9->4->5->NULL
    L2 = 2->4->6->NULL

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

Please share if there is something wrong or missing. If you are interested in contributing to algorithmsandme, please contact us.