Add two numbers represented by linked lists | Set 1 - GeeksforGeeks

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

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.

/* 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;

}

http://yuanhsh.iteye.com/blog/2181044

1. public ListNode addLinkedList(ListNode a, ListNode b) {  
2.     ListNode result = new ListNode(0);  
3.     ListNode dummy = result;  
4.     int carry = 0;  
5.     while(a!=null || b!=null) {  
6.         int sum = carry + ((a!=null)?a.val:0) + ((b!=null)?b.val:0);  
7.         carry = sum / 10;  
8.         result.next = new ListNode(sum%10);  
9.         result = result.next;  
10.         if(a!=null) a=a.next;  
11.         if(b!=null) b=b.next;  
12.     }  
13.     if(carry>0) {  
14.         result.next = new ListNode(carry);  
15.     }  
16.     return dummy.next;  
17. }  

Read full article from Add two numbers represented by linked lists | Set 1 - GeeksforGeeks