Given two numbers represented by two linked lists, write a function that returns the sum of the two linked lists in the form of a list.
Note: It is not allowed to modify the lists. Also, not allowed to use explicit extra space (Hint: Use Recursion).
Example :
Input: First List: 5->6->3, Second List: 8->4->2
Output: Resultant list: 1->4->0->5
Explanation: Sum of 563 and 842 is 1405
We have discussed a solution here which is for linked lists where the least significant digit is the first node of lists and the most significant digit is the last node. In this problem, the most significant digit is the first node and the least significant digit is the last node and we are not allowed to modify the lists. Recursion is used here to calculate the sum from right to left.
Following are the steps.
1) Calculate sizes of given two linked lists.
2) If sizes are same, then calculate sum using recursion. Hold all nodes in recursion call stack till the rightmost node, calculate the sum of rightmost nodes and forward carry to the left side.
3) If size is not same, then follow below steps:
….a) Calculate difference of sizes of two linked lists. Let the difference be diff
….b) Move diff nodes ahead in the bigger linked list. Now use step 2 to calculate the sum of the smaller list and right sub-list (of the same size) of a larger list. Also, store the carry of this sum.
….c) Calculate the sum of the carry (calculated in the previous step) with the remaining left sub-list of a larger list. Nodes of this sum are added at the beginning of the sum list obtained the previous step.
Below is a dry run of the above approach:
Below is the implementation of the above approach.
C++
// A C++ recursive program to add two linked lists#include <bits/stdc++.h>using namespace std;// A linked List Nodeclass Node {public: int data; Node* next;};typedef Node node;/* A utility function to inserta node at the beginning of linked list */void push(Node** head_ref, int new_data){ /* allocate node */ Node* new_node = new Node[(sizeof(Node))]; /* put in the data */ new_node->data = new_data; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node;}/* A utility function to print linked list */void printList(Node* node){ while (node != NULL) { cout << node->data << " "; node = node->next; } cout << endl;}// A utility function to swap two pointersvoid swapPointer(Node** a, Node** b){ node* t = *a; *a = *b; *b = t;}/* A utility function to get size of linked list */int getSize(Node* node){ int size = 0; while (node != NULL) { node = node->next; size++; } return size;}// Adds two linked lists of same size// represented by head1 and head2 and returns// head of the resultant linked list. Carry// is propagated while returning from the recursionnode* addSameSize(Node* head1, Node* head2, int* carry){ // Since the function assumes linked lists are of same // size, check any of the two head pointers if (head1 == NULL) return NULL; int sum; // Allocate memory for sum node of current two nodes Node* result = new Node[(sizeof(Node))]; // Recursively add remaining nodes and get the carry result->next = addSameSize(head1->next, head2->next, carry); // add digits of current nodes and propagated carry sum = head1->data + head2->data + *carry; *carry = sum / 10; sum = sum % 10; // Assign the sum to current node of resultant list result->data = sum; return result;}// This function is called after the// smaller list is added to the bigger// lists's sublist of same size. Once the// right sublist is added, the carry// must be added toe left side of larger// list to get the final result.void addCarryToRemaining(Node* head1, Node* cur, int* carry, Node** result){ int sum; // If diff. number of nodes are not traversed, add carry if (head1 != cur) { addCarryToRemaining(head1->next, cur, carry, result); sum = head1->data + *carry; *carry = sum / 10; sum %= 10; // add this node to the front of the result push(result, sum); }}// The main function that adds two linked lists// represented by head1 and head2. The sum of// two lists is stored in a list referred by resultvoid addList(Node* head1, Node* head2, Node** result){ Node* cur; // first list is empty if (head1 == NULL) { *result = head2; return; } // second list is empty else if (head2 == NULL) { *result = head1; return; } int size1 = getSize(head1); int size2 = getSize(head2); int carry = 0; // Add same size lists if (size1 == size2) *result = addSameSize(head1, head2, &carry); else { int diff = abs(size1 - size2); // First list should always be larger than second // list. If not, swap pointers if (size1 < size2) swapPointer(&head1, &head2); // move diff. number of nodes in first list for (cur = head1; diff--; cur = cur->next) ; // get addition of same size lists *result = addSameSize(cur, head2, &carry); // get addition of remaining first list and carry addCarryToRemaining(head1, cur, &carry, result); } // if some carry is still there, add a new node to the // front of the result list. e.g. 999 and 87 if (carry) push(result, carry);}// Driver codeint main(){ Node *head1 = NULL, *head2 = NULL, *result = NULL; int arr1[] = { 9, 9, 9 }; int arr2[] = { 1, 8 }; int size1 = sizeof(arr1) / sizeof(arr1[0]); int size2 = sizeof(arr2) / sizeof(arr2[0]); // Create first list as 9->9->9 int i; for (i = size1 - 1; i >= 0; --i) push(&head1, arr1[i]); // Create second list as 1->8 for (i = size2 - 1; i >= 0; --i) push(&head2, arr2[i]); addList(head1, head2, &result); printList(result); return 0;}// This code is contributed by rathbhupendra |
C
// A C recursive program to add two linked lists#include <stdio.h>#include <stdlib.h>// A linked List Nodestruct Node { int data; struct Node* next;};typedef struct Node node;/* A utility function to insert a node at the beginning of * linked list */void push(struct Node** head_ref, int new_data){ /* allocate node */ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node;}/* A utility function to print linked list */void printList(struct Node* node){ while (node != NULL) { printf("%d ", node->data); node = node->next; } printf("n");}// A utility function to swap two pointersvoid swapPointer(Node** a, Node** b){ node* t = *a; *a = *b; *b = t;}/* A utility function to get size of linked list */int getSize(struct Node* node){ int size = 0; while (node != NULL) { node = node->next; size++; } return size;}// Adds two linked lists of same // size represented by head1// and head2 and returns head of // the resultant linked list.// Carry is propagated while // returning from the recursionnode* addSameSize(Node* head1, Node* head2, int* carry){ // Since the function assumes // linked lists are of same // size, check any of the two // head pointers if (head1 == NULL) return NULL; int sum; // Allocate memory for sum // node of current two nodes Node* result = (Node*)malloc(sizeof(Node)); // Recursively add remaining nodes // and get the carry result->next = addSameSize(head1->next, head2->next, carry); // add digits of current nodes // and propagated carry sum = head1->data + head2->data + *carry; *carry = sum / 10; sum = sum % 10; // Assigne the sum to current // node of resultant list result->data = sum; return result;}// This function is called after // the smaller list is added// to the bigger lists's sublist // of same size. Once the// right sublist is added, the // carry must be added toe left// side of larger list to get // the final result.void addCarryToRemaining(Node* head1, Node* cur, int* carry, Node** result){ int sum; // If diff. number of nodes are // not traversed, add carry if (head1 != cur) { addCarryToRemaining(head1->next, cur, carry, result); sum = head1->data + *carry; *carry = sum / 10; sum %= 10; // add this node to the front of the result push(result, sum); }}// The main function that adds two // linked lists represented// by head1 and head2. The sum of// two lists is stored in a// list referred by resultvoid addList(Node* head1, Node* head2, Node** result){ Node* cur; // first list is empty if (head1 == NULL) { *result = head2; return; } // second list is empty else if (head2 == NULL) { *result = head1; return; } int size1 = getSize(head1); int size2 = getSize(head2); int carry = 0; // Add same size lists if (size1 == size2) *result = addSameSize(head1, head2, &carry); else { int diff = abs(size1 - size2); // First list should always be // larger than second // list. If not, swap pointers if (size1 < size2) swapPointer(&head1, &head2); // move diff. number of nodes in first list for (cur = head1; diff--; cur = cur->next) ; // get addition of same size lists *result = addSameSize(cur, head2, &carry); // get addition of remaining first list and carry addCarryToRemaining(head1, cur, &carry, result); } // if some carry is still there, add a new node to the // front of the result list. e.g. 999 and 87 if (carry) push(result, carry);}// Driver codeint main(){ Node *head1 = NULL, *head2 = NULL, *result = NULL; int arr1[] = { 9, 9, 9 }; int arr2[] = { 1, 8 }; int size1 = sizeof(arr1) / sizeof(arr1[0]); int size2 = sizeof(arr2) / sizeof(arr2[0]); // Create first list as 9->9->9 int i; for (i = size1 - 1; i >= 0; --i) push(&head1, arr1[i]); // Create second list as 1->8 for (i = size2 - 1; i >= 0; --i) push(&head2, arr2[i]); addList(head1, head2, &result); printList(result); return 0;} |
Java
// A Java recursive program to add two linked listspublic class linkedlistATN { class node { int val; node next; public node(int val) { this.val = val; } } // Function to print linked list void printlist(node head) { while (head != null) { System.out.print(head.val + " "); head = head.next; } } node head1, head2, result; int carry; /* A utility function to push a value to linked list */ void push(int val, int list) { node newnode = new node(val); if (list == 1) { newnode.next = head1; head1 = newnode; } else if (list == 2) { newnode.next = head2; head2 = newnode; } else { newnode.next = result; result = newnode; } } // Adds two linked lists of same size represented by // head1 and head2 and returns head of the resultant // linked list. Carry is propagated while returning // from the recursion void addsamesize(node n, node m) { // Since the function assumes linked lists are of // same size, check any of the two head pointers if (n == null) return; // Recursively add remaining nodes and get the carry addsamesize(n.next, m.next); // add digits of current nodes and propagated carry int sum = n.val + m.val + carry; carry = sum / 10; sum = sum % 10; // Push this to result list push(sum, 3); } node cur; // This function is called after the smaller list is // added to the bigger lists's sublist of same size. // Once the right sublist is added, the carry must be // added to the left side of larger list to get the // final result. void propogatecarry(node head1) { // If diff. number of nodes are not traversed, add carry if (head1 != cur) { propogatecarry(head1.next); int sum = carry + head1.val; carry = sum / 10; sum %= 10; // add this node to the front of the result push(sum, 3); } } int getsize(node head) { int count = 0; while (head != null) { count++; head = head.next; } return count; } // The main function that adds two linked lists // represented by head1 and head2. The sum of two // lists is stored in a list referred by result void addlists() { // first list is empty if (head1 == null) { result = head2; return; } // first list is empty if (head2 == null) { result = head1; return; } int size1 = getsize(head1); int size2 = getsize(head2); // Add same size lists if (size1 == size2) { addsamesize(head1, head2); } else { // First list should always be larger than second list. // If not, swap pointers if (size1 < size2) { node temp = head1; head1 = head2; head2 = temp; } int diff = Math.abs(size1 - size2); // move diff. number of nodes in first list node temp = head1; while (diff-- >= 0) { cur = temp; temp = temp.next; } // get addition of same size lists addsamesize(cur, head2); // get addition of remaining first list and carry propogatecarry(head1); } // if some carry is still there, add a new node to // the front of the result list. e.g. 999 and 87 if (carry > 0) push(carry, 3); } // Driver program to test above functions public static void main(String args[]) { linkedlistATN list = new linkedlistATN(); list.head1 = null; list.head2 = null; list.result = null; list.carry = 0; int arr1[] = { 9, 9, 9 }; int arr2[] = { 1, 8 }; // Create first list as 9->9->9 for (int i = arr1.length - 1; i >= 0; --i) list.push(arr1[i], 1); // Create second list as 1->8 for (int i = arr2.length - 1; i >= 0; --i) list.push(arr2[i], 2); list.addlists(); list.printlist(list.result); }}// This code is contributed by Rishabh Mahrsee |
Python3
# A Python3 recursive program to add two linked listsclass node: def __init__(self, val): self.val = val self.next = Nonehead1, head2, result = None, None, Nonecarry = 0# Function to print linked listdef printlist(head): while head != None: print(head.val, end=" ") head = head.next# A utility function to push a value to linked listdef push(val, lst): global head1, head2, result newnode = node(val) if lst == 1: newnode.next = head1 head1 = newnode elif lst == 2: newnode.next = head2 head2 = newnode else: newnode.next = result result = newnode# Adds two linked lists of same size represented by# head1 and head2 and returns head of the resultant# linked list. Carry is propagated while returning# from the recursiondef addsamesize(n, m): global carry # Since the function assumes linked lists are of # same size, check any of the two head pointers if n == None: return # Recursively add remaining nodes and get the carry addsamesize(n.next, m.next) # add digits of current nodes and propagated carry sum = n.val + m.val + carry carry = int(sum / 10) sum = sum % 10 # Push this to result list push(sum, 3)cur = None# This function is called after the smaller list is# added to the bigger lists's sublist of same size.# Once the right sublist is added, the carry must be# added to the left side of larger list to get the# final result.def propogatecarry(head1): global carry, cur # If diff. number of nodes are not traversed, add carry if head1 != cur: propogatecarry(head1.next) sum = carry + head1.val carry = int(sum / 10) sum %= 10 # add this node to the front of the result push(sum, 3)def getsize(head): count = 0 while head != None: count += 1 head = head.next return count # The main function that adds two linked lists# represented by head1 and head2. The sum of two# lists is stored in a list referred by resultdef addlists(): global head1, head2, result, carry, cur # first list is empty if head1 == None: result = head2 return # first list is empty if head2 == None: result = head1 return size1 = getsize(head1) size2 = getsize(head2) # Add same size lists if size1 == size2: addsamesize(head1, head2) else: # First list should always be larger than second list. # If not, swap pointers if size1 < size2: temp = head1 head1 = head2 head2 = temp diff = abs(size1 - size2) # move diff. number of nodes in first list temp = head1 while diff >= 0: cur = temp temp = temp.next diff -= 1 # get addition of same size lists addsamesize(cur, head2) # get addition of remaining first list and carry propogatecarry(head1) # if some carry is still there, add a new node to # the front of the result list. e.g. 999 and 87 if carry > 0: push(carry, 3)# Driver program to test above functionshead1, head2, result = None, None, Nonecarry = 0arr1 = [9, 9, 9]arr2 = [1, 8]# Create first list as 9->9->9for i in range(len(arr1)-1, -1, -1): push(arr1[i], 1)# Create second list as 1->8for i in range(len(arr2)-1, -1, -1): push(arr2[i], 2)addlists()printlist(result)# This code is contributed by Prajwal Kandekar |
C#
// A C# recursive program to add two linked listsusing System; public class linkedlistATN{ class node { public int val; public node next; public node(int val) { this.val = val; }} // Function to print linked listvoid printlist(node head) { while (head != null) { Console.Write(head.val + " "); head = head.next; }}node head1, head2, result;int carry;// A utility function to push a // value to linked list void push(int val, int list) { node newnode = new node(val); if (list == 1) { newnode.next = head1; head1 = newnode; } else if (list == 2) { newnode.next = head2; head2 = newnode; } else { newnode.next = result; result = newnode; }}// Adds two linked lists of same size represented by// head1 and head2 and returns head of the resultant // linked list. Carry is propagated while returning // from the recursionvoid addsamesize(node n, node m) { // Since the function assumes linked // lists are of same size, check any // of the two head pointers if (n == null) return; // Recursively add remaining nodes // and get the carry addsamesize(n.next, m.next); // Add digits of current nodes // and propagated carry int sum = n.val + m.val + carry; carry = sum / 10; sum = sum % 10; // Push this to result list push(sum, 3);}node cur;// This function is called after the smaller // list is added to the bigger lists's sublist // of same size. Once the right sublist is added,// the carry must be added to the left side of // larger list to get the final result.void propogatecarry(node head1) { // If diff. number of nodes are // not traversed, add carry if (head1 != cur) { propogatecarry(head1.next); int sum = carry + head1.val; carry = sum / 10; sum %= 10; // Add this node to the front // of the result push(sum, 3); }}int getsize(node head) { int count = 0; while (head != null) { count++; head = head.next; } return count;}// The main function that adds two linked // lists represented by head1 and head2. // The sum of two lists is stored in a // list referred by resultvoid addlists() { // First list is empty if (head1 == null) { result = head2; return; } // Second list is empty if (head2 == null) { result = head1; return; } int size1 = getsize(head1); int size2 = getsize(head2); // Add same size lists if (size1 == size2) { addsamesize(head1, head2); } else { // First list should always be // larger than second list. // If not, swap pointers if (size1 < size2) { node temp = head1; head1 = head2; head2 = temp; } int diff = Math.Abs(size1 - size2); // Move diff. number of nodes in // first list node tmp = head1; while (diff-- >= 0) { cur = tmp; tmp = tmp.next; } // Get addition of same size lists addsamesize(cur, head2); // Get addition of remaining // first list and carry propogatecarry(head1); } // If some carry is still there, // add a new node to the front of // the result list. e.g. 999 and 87 if (carry > 0) push(carry, 3);}// Driver codepublic static void Main(string []args){ linkedlistATN list = new linkedlistATN(); list.head1 = null; list.head2 = null; list.result = null; list.carry = 0; int []arr1 = { 9, 9, 9 }; int []arr2 = { 1, 8 }; // Create first list as 9->9->9 for(int i = arr1.Length - 1; i >= 0; --i) list.push(arr1[i], 1); // Create second list as 1->8 for(int i = arr2.Length - 1; i >= 0; --i) list.push(arr2[i], 2); list.addlists(); list.printlist(list.result);}}// This code is contributed by rutvik_56 |
Javascript
<script>// A javascript recursive program to add two linked lists class node { constructor(val) { this.val = val; this.next = null; } } // Function to print linked list function printlist( head) { while (head != null) { document.write(head.val + " "); head = head.next; } } var head1, head2, result; var carry; /* A utility function to push a value to linked list */ function push(val , list) { var newnode = new node(val); if (list == 1) { newnode.next = head1; head1 = newnode; } else if (list == 2) { newnode.next = head2; head2 = newnode; } else { newnode.next = result; result = newnode; } } // Adds two linked lists of same size represented by // head1 and head2 and returns head of the resultant // linked list. Carry is propagated while returning // from the recursion function addsamesize( n, m) { // Since the function assumes linked lists are of // same size, check any of the two head pointers if (n == null) return; // Recursively add remaining nodes and get the carry addsamesize(n.next, m.next); // add digits of current nodes and propagated carry var sum = n.val + m.val + carry; carry = parseInt(sum / 10); sum = sum % 10; // Push this to result list push(sum, 3); } var cur; // This function is called after the smaller list is // added to the bigger lists's sublist of same size. // Once the right sublist is added, the carry must be // added to the left side of larger list to get the // final result. function propogatecarry( head1) { // If diff. number of nodes are not traversed, add carry if (head1 != cur) { propogatecarry(head1.next); var sum = carry + head1.val; carry = parseInt(sum / 10); sum %= 10; // add this node to the front of the result push(sum, 3); } } function getsize( head) { var count = 0; while (head != null) { count++; head = head.next; } return count; } // The main function that adds two linked lists // represented by head1 and head2. The sum of two // lists is stored in a list referred by result function addlists() { // first list is empty if (head1 == null) { result = head2; return; } // first list is empty if (head2 == null) { result = head1; return; } var size1 = getsize(head1); var size2 = getsize(head2); // Add same size lists if (size1 == size2) { addsamesize(head1, head2); } else { // First list should always be larger than second list. // If not, swap pointers if (size1 < size2) { var temp = head1; head1 = head2; head2 = temp; } var diff = Math.abs(size1 - size2); // move diff. number of nodes in first list var temp = head1; while (diff-- >= 0) { cur = temp; temp = temp.next; } // get addition of same size lists addsamesize(cur, head2); // get addition of remaining first list and carry propogatecarry(head1); } // if some carry is still there, add a new node to // the front of the result list. e.g. 999 and 87 if (carry > 0) push(carry, 3); } // Driver program to test above functions head1 = null; head2 = null; result = null; carry = 0; var arr1 = [ 9, 9, 9 ]; var arr2 = [ 1, 8 ]; // Create first list as 9->9->9 for (i = arr1.length - 1; i >= 0; --i) push(arr1[i], 1); // Create second list as 1->8 for (i = arr2.length - 1; i >= 0; --i) push(arr2[i], 2); addlists(); printlist(result);// This code is contributed by todaysgaurav</script> |
Output
1 0 1 7
Time Complexity: O(m+n) where m and n are the sizes of given two linked lists.
Auxiliary Space: O(m+n) for call stack
Iterative Approach:
This implementation does not have any recursion call overhead, which means it is an iterative solution.
Since we need to start adding numbers from the last of the two linked lists. So, here we will use the stack data structure to implement this.
- We will firstly make two stacks from the given two linked lists.
- Then, we will run a loop till both stack become empty.
- in every iteration, we keep the track of the carry.
- In the end, if carry>0, that means we need extra node at the start of the resultant list to accommodate this carry.
Below is the implementation of the above approach.
C++
// C++ Iterative program to add two linked lists #include <bits/stdc++.h> using namespace std; // A linked List Node class Node { public: int data; Node* next; };// to push a new node to linked listvoid push(Node** head_ref, int new_data) { /* allocate node */ Node* new_node = new Node[(sizeof(Node))]; /* put in the data */ new_node->data = new_data; /* link the old list of the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; }// to add two new numbersNode* addTwoNumList(Node* l1, Node* l2) { stack<int> s1,s2; while(l1!=NULL){ s1.push(l1->data); l1=l1->next; } while(l2!=NULL){ s2.push(l2->data); l2=l2->next; } int carry=0; Node* result=NULL; while(s1.empty()==false || s2.empty()==false){ int a=0,b=0; if(s1.empty()==false){ a=s1.top();s1.pop(); } if(s2.empty()==false){ b=s2.top();s2.pop(); } int total=a+b+carry; Node* temp=new Node(); temp->data=total%10; carry=total/10; if(result==NULL){ result=temp; }else{ temp->next=result; result=temp; } } if(carry!=0){ Node* temp=new Node(); temp->data=carry; temp->next=result; result=temp; } return result;}// to print a linked listvoid printList(Node *node) { while (node != NULL) { cout<<node->data<<" "; node = node->next; } cout<<endl; }// Driver Codeint main() { Node *head1 = NULL, *head2 = NULL; int arr1[] = {5, 6, 7}; int arr2[] = {1, 8}; int size1 = sizeof(arr1) / sizeof(arr1[0]); int size2 = sizeof(arr2) / sizeof(arr2[0]); // Create first list as 5->6->7 int i; for (i = size1-1; i >= 0; --i) push(&head1, arr1[i]); // Create second list as 1->8 for (i = size2-1; i >= 0; --i) push(&head2, arr2[i]); Node* result=addTwoNumList(head1, head2); printList(result); return 0; } |
Java
// Java Iterative program to add // two linked lists import java.io.*;import java.util.*;class GFG{ static class Node{ int data; Node next; public Node(int data) { this.data = data; }}static Node l1, l2, result;// To push a new node to linked listpublic static void push(int new_data){ // Allocate node Node new_node = new Node(0); // Put in the data new_node.data = new_data; // Link the old list of the new node new_node.next = l1; // Move the head to point to the new node l1 = new_node;}public static void push1(int new_data){ // Allocate node Node new_node = new Node(0); // Put in the data new_node.data = new_data; // Link the old list of the new node new_node.next = l2; // Move the head to point to // the new node l2 = new_node;}// To add two new numberspublic static Node addTwoNumbers(){ Stack<Integer> stack1 = new Stack<>(); Stack<Integer> stack2 = new Stack<>(); while (l1 != null) { stack1.add(l1.data); l1 = l1.next; } while (l2 != null) { stack2.add(l2.data); l2 = l2.next; } int carry = 0; Node result = null; while (!stack1.isEmpty() || !stack2.isEmpty()) { int a = 0, b = 0; if (!stack1.isEmpty()) { a = stack1.pop(); } if (!stack2.isEmpty()) { b = stack2.pop(); } int total = a + b + carry; Node temp = new Node(total % 10); carry = total / 10; if (result == null) { result = temp; } else { temp.next = result; result = temp; } } if (carry != 0) { Node temp = new Node(carry); temp.next = result; result = temp; } return result;}// To print a linked listpublic static void printList(){ while (result != null) { System.out.print(result.data + " "); result = result.next; } System.out.println();}// Driver codepublic static void main(String[] args){ int arr1[] = { 5, 6, 7 }; int arr2[] = { 1, 8 }; int size1 = 3; int size2 = 2; // Create first list as 5->6->7 int i; for(i = size1 - 1; i >= 0; --i) push(arr1[i]); // Create second list as 1->8 for(i = size2 - 1; i >= 0; --i) push1(arr2[i]); result = addTwoNumbers(); printList();}}// This code is contributed by RohitOberoi |
Python3
# Python Iterative program to add# two linked lists class Node: def __init__(self,val): self.data = val self.next = None l1, l2, result = None,None,0# To push a new node to linked listdef push(new_data): global l1 # Allocate node new_node = Node(0) # Put in the data new_node.data = new_data # Link the old list of the new node new_node.next = l1 # Move the head to point to the new node l1 = new_nodedef push1(new_data): global l2 # Allocate node new_node = Node(0) # Put in the data new_node.data = new_data # Link the old list of the new node new_node.next = l2 # Move the head to point to # the new node l2 = new_node# To add two new numbersdef addTwoNumbers(): global l1,l2,result stack1 = [] stack2 = [] while (l1 != None): stack1.append(l1.data) l1 = l1.next while (l2 != None): stack2.append(l2.data) l2 = l2.next carry = 0 result = None while (len(stack1) != 0 or len(stack2) != 0): a,b = 0,0 if (len(stack1) != 0): a = stack1.pop() if (len(stack2) != 0): b = stack2.pop() total = a + b + carry temp = Node(total % 10) carry = total // 10 if (result == None): result = temp else: temp.next = result result = temp if (carry != 0): temp = Node(carry) temp.next = result result = temp return result# To print a linked listdef printList(): global result while (result != None): print(result.data ,end = " ") result = result.next# Driver code arr1 = [ 5, 6, 7 ]arr2 = [ 1, 8 ]size1 = 3size2 = 2# Create first list as 5->6->7for i in range(size1-1,-1,-1): push(arr1[i])# Create second list as 1->8for i in range(size2-1,-1,-1): push1(arr2[i])result = addTwoNumbers()printList()# This code is contributed by shinjanpatra |
C#
// C# Iterative program to add // two linked lists using System;using System.Collections;class GFG{ public class Node { public int data; public Node next; public Node(int data) { this.data = data; } } static Node l1, l2, result; // To push a new node to linked list public static void push(int new_data) { // Allocate node Node new_node = new Node(0); // Put in the data new_node.data = new_data; // Link the old list of the new node new_node.next = l1; // Move the head to point to the new node l1 = new_node; } public static void push1(int new_data) { // Allocate node Node new_node = new Node(0); // Put in the data new_node.data = new_data; // Link the old list of the new node new_node.next = l2; // Move the head to point to // the new node l2 = new_node; } // To add two new numbers public static Node addTwoNumbers() { Stack stack1 = new Stack(); Stack stack2 = new Stack(); while (l1 != null) { stack1.Push(l1.data); l1 = l1.next; } while (l2 != null) { stack2.Push(l2.data); l2 = l2.next; } int carry = 0; Node result = null; while (stack1.Count != 0 || stack2.Count != 0) { int a = 0, b = 0; if (stack1.Count != 0) { a = (int)stack1.Pop(); } if (stack2.Count != 0) { b = (int)stack2.Pop(); } int total = a + b + carry; Node temp = new Node(total % 10); carry = total / 10; if (result == null) { result = temp; } else { temp.next = result; result = temp; } } if (carry != 0) { Node temp = new Node(carry); temp.next = result; result = temp; } return result; } // To print a linked list public static void printList() { while (result != null) { Console.Write(result.data + " "); result = result.next; } Console.WriteLine(); } // Driver code public static void Main(string[] args) { int []arr1 = { 5, 6, 7 }; int []arr2 = { 1, 8 }; int size1 = 3; int size2 = 2; // Create first list as 5->6->7 int i; for(i = size1 - 1; i >= 0; --i) push(arr1[i]); // Create second list as 1->8 for(i = size2 - 1; i >= 0; --i) push1(arr2[i]); result = addTwoNumbers(); printList(); }}// This code is contributed by pratham76 |
Javascript
<script>// javascript Iterative program to add // two linked lists class Node { constructor(val) { this.data = val; this.next = null; }} var l1, l2, result; // To push a new node to linked list function push(new_data) { // Allocate nodevar new_node = new Node(0); // Put in the data new_node.data = new_data; // Link the old list of the new node new_node.next = l1; // Move the head to point to the new node l1 = new_node; } function push1(new_data) { // Allocate nodevar new_node = new Node(0); // Put in the data new_node.data = new_data; // Link the old list of the new node new_node.next = l2; // Move the head to point to // the new node l2 = new_node; } // To add two new numbers function addTwoNumbers() { var stack1 = []; var stack2 = []; while (l1 != null) { stack1.push(l1.data); l1 = l1.next; } while (l2 != null) { stack2.push(l2.data); l2 = l2.next; } var carry = 0;var result = null; while (stack1.length != 0 || stack2.length != 0) { var a = 0, b = 0; if (stack1.length != 0) { a = stack1.pop(); } if (stack2.length != 0) { b = stack2.pop(); } var total = a + b + carry; var temp = new Node(total % 10); carry = parseInt(total / 10); if (result == null) { result = temp; } else { temp.next = result; result = temp; } } if (carry != 0) { var temp = new Node(carry); temp.next = result; result = temp; } return result; } // To print a linked list function printList() { while (result != null) { document.write(result.data + " "); result = result.next; } document.write(); } // Driver code var arr1 = [ 5, 6, 7 ]; var arr2 = [ 1, 8 ]; var size1 = 3; var size2 = 2; // Create first list as 5->6->7 var i; for (var i = size1 - 1; i >= 0; --i) push(arr1[i]); // Create second list as 1->8 for (i = size2 - 1; i >= 0; --i) push1(arr2[i]); result = addTwoNumbers(); printList();// This code contributed by umadevi9616 </script> |
Output
5 8 5
Time Complexity: O(m+n) where m and n are the sizes of given two linked lists.
Auxiliary Space: O(m+n)
Another Approach (Simple iteration with 2 pointers)
To add two numbers in a linked list, 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 :
- Use 2 pointers to store the head of each linked list and initialize carry as 0.
- Declare a pointer to the node to store our answer.
- Iterate through both the linked list and add the digits pointed by the pointers (if we have reached the end of one of the linked lists and have no further nodes, consider its value as 0 while taking the sum).
- Add a new node with ((sum+carry)%10) as value to our answer and update carry as (sum + carry)/10.
- Repeat steps 3 and 4 till we reach the end of both the linked lists.
- After traversing both the linked lists, if carry > 0 then add this carry to our answer as a new node.
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 listsNode* 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, 1); push_front(&l1, 5); Node* l2 = NULL; push_front(&l2, 3); push_front(&l2, 9); push_front(&l2, 7); // l1-> 5 1 = 15 // l2-> 7 9 3 = 397 Node* sum = add(l1,l2); printList(sum); // 2 1 4 = 412} |
Java
/*package whatever //do not write package name here */class Node { int val; Node next; Node(int value) { val = value; next = null; }}class AddTwoLL { static void push_front(Node head, int new_val) { Node new_node = new Node(new_val); new_node.next =head; head = new_node; } static void printList(Node head) { Node i = head; while(i!=null) { System.out.print(i.val+" "); i = i.next; } System.out.println(); } // function to reverse a linked list static 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 integer static int to_integer(Node head){ int num = 0; Node curr = head; while(curr!=null) { 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 static Node to_linkedlist(int x) { Node head = new Node(0); if(x==0) return head; Node curr = head; while(x>0) { 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 static 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; } public static void main(String [] args) { Node l1 = null; push_front(l1, 1); push_front(l1, 5); Node l2 = null; push_front(l2, 3); push_front(l2, 9); push_front(l2, 7); // l1-> 5 1 // l2-> 7 9 3 Node sum = add_list(l1,l2); printList(sum); // 2 1 4 }} |
Python3
# Add two numbers represented by linked lists | Set 2class Node: def __init__(self, value): self.val = value self.next = Nonedef push_front(head, new_val): new_node = Node(new_val) new_node.next = head head = new_node return headdef print_list(head): i = head while i: print(i.val, end=" ") i = i.next print()def add(l1, l2): ans = Node(0) curr = ans carry = 0 while l1 or l2: sum_val = 0 if l1: sum_val += l1.val l1 = l1.next if l2: sum_val += l2.val l2 = l2.next sum_val += carry curr.next = Node(sum_val % 10) curr = curr.next carry = sum_val // 10 if carry: curr.next = Node(carry) ans = ans.next return ans# Creating linked list l1: 5 -> 1l1 = Nonel1 = push_front(l1, 1)l1 = push_front(l1, 5)# Creating linked list l2: 7 -> 9 -> 3l2 = Nonel2 = push_front(l2, 3)l2 = push_front(l2, 9)l2 = push_front(l2, 7)# l1: 5 -> 1 = 15# l2: 7 -> 9 -> 3 = 397# Adding two linked listssum_list = add(l1, l2)# Printing the resulting linked listprint_list(sum_list)# Output: 2 1 4 = 412# This code is contributed by uomkar369 |
Output
2 1 4
Time Complexity: O(n).
Space Complexity: O(max(n,m))
To avoid the use of extra space we can store the sum in one of the linked lists itself.
Related Article: Add two numbers represented by linked lists | Set 1
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
