Saturday, September 20, 2014

LeetCode: Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
    
   typedef ListNode ln;  
   
   int count(ln *head)  
   {  
     int cnt = 0;  
     while(head){  
       head = head->next;  
       cnt++;  
     }  
     return cnt;  
   }  
   
   ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {  
     if(l1 == NULL && l2 == NULL)return NULL;  
     if(l1 == NULL)return l2;  
     if(l2 == NULL)return l1;  
   
     ln *head = NULL,*last;  
     int sum = 0, carry = 0;  
   
     while(l1 && l2)  
     {  
       sum = l1->val + l2->val + carry;  
       carry = sum/10;  
       sum = sum%10;  
       ln *n = new ln(sum);  
       if(!head){head = n; last = head;}  
       else  
       {  
         last->next = n;  
         last = n;  
       }  
   
       l1 = l1->next;  
       l2 = l2->next;  
     }  
   
     while(l1)  
     {  
       sum = l1->val + carry;  
       carry = sum/10;  
       last->next = new ln(sum%10);  
       l1 = l1->next;  
       last = last->next;  
     }  
   
     while(l2)  
     {  
       sum = l2->val + carry;  
       carry = sum/10;  
       last->next = new ln(sum%10);  
       l2 = l2->next;  
       last = last->next;  
     }  
   
     if (carry)last->next = new ln(carry);  
   
     return head;  
   }  

No comments:

Post a Comment