Add two numbers represented by linked lists | Set 1 - GeeksforGeeks
Given two numbers represented by two lists, write a function that returns sum list. The sum list is list representation of addition of two input numbers.
Example 1
Given two numbers represented by two lists, write a function that returns sum list. The sum list is list representation of addition of two input numbers.
Example 1
Input: First List: 5->6->3 // represents number 365
Second List: 8->4->2 // represents number 248 Output
Resultant list: 3->1->6 // represents number 613
Input: First List: 7->5->9->4->6 // represents number 64957 Second List: 8->4 // represents number 48 Output Resultant list: 5->0->0->5->6 // represents number 65005
Traverse both lists. One by one pick nodes of both lists and add the values. If sum is more than 10 then make carry as 1 and reduce sum. If one list has more elements than the other then consider remaining values of this list as 0. Following is Java implementation of this approach.
http://yuanhsh.iteye.com/blog/2181044
/* Adds contents of two linked lists and return the head node of resultant list */struct node* addTwoLists (struct node* first, struct node* second){ struct node* res = NULL; // res is head node of the resultant list struct node *temp, *prev = NULL; int carry = 0, sum; while (first != NULL || second != NULL) //while both lists exist { // 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 calulation 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; else // If this is not the first node then connect it to the rest. 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;}- public ListNode addLinkedList(ListNode a, ListNode b) {
- ListNode result = new ListNode(0);
- ListNode dummy = result;
- int carry = 0;
- while(a!=null || b!=null) {
- int sum = carry + ((a!=null)?a.val:0) + ((b!=null)?b.val:0);
- carry = sum / 10;
- result.next = new ListNode(sum%10);
- result = result.next;
- if(a!=null) a=a.next;
- if(b!=null) b=b.next;
- }
- if(carry>0) {
- result.next = new ListNode(carry);
- }
- return dummy.next;
- }
