leetcode Question 5: 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


Analysis:
The idea is simple, add each element of two list with the help of a variable "carry". When both of the lists meet their end, return result.
The key point is to check the carry before return, if carry = 1 the highest bit should be 1, that means add a new node with value "1" to the result list. 
e.g. (9->null) + (1->null) = (0->1->null)

Code(Updated 201309):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int carry=0;
        ListNode* res=new ListNode(0);
        ListNode* head = res;
        while (l1 && l2){
            res->next=new ListNode((l1->val+l2->val+carry)%10);
            carry = (l1->val+l2->val+carry)/10;
            l1=l1->next;
            l2=l2->next;
            res=res->next;
        }
        
        while (l1){
            res->next=new ListNode((l1->val+carry)%10);
            carry = (l1->val+carry)/10;
            l1=l1->next;
            res=res->next;
        }
        
        while (l2){
            res->next=new ListNode((l2->val+carry)%10);
            carry = (l2->val+carry)/10;
            l2=l2->next;
            res=res->next;
        }
        
        if (carry>0){
            res->next = new ListNode(carry);
        }
        
        return head->next;
        
    }
};

5 comments:

  1. adding right to left is the natural way..
    243 will be 2->4->3
    123 will be 1->2->3
    here adding must b from right to left..
    left to right is easy!!

    ReplyDelete
    Replies
    1. Yes, that is the natural way of doing that, here just give an idea of how the problem be solved.
      And this is the same question in the book Cracking the Coding Interview, I remember it's in Chapter 1.
      You can find more details there!

      Enjoy!

      Delete
  2. if (l1 && l2)??

    missing some scenarios...

    ReplyDelete
  3. forget to delete head, casue memory leak

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete