2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. 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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

Solution 1:

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
12         int cnt=0,size_l1=0,size_l2=0;
13         ListNode* res=new ListNode(0);
14         ListNode* t=l1;
15         int carry=0;
16         while(t){
17             size_l1++;
18             t=t->next;
19         }
20         t=l2;
21         while(t){
22             size_l2++;
23             t=t->next;
24         }
25 
26         ListNode* s=res;
27         ListNode* c;
28         while(cnt<min(size_l1,size_l2)){
29             int sum=l1->val+l2->val+carry;
30             s->val=sum%10;
31             if(s->next==NULL)c=s;
32             s=s->next;            
33             l1=l1->next;
34             l2=l2->next;
35             carry=sum/10;
36             cnt++;
37         }
38         if (size_l1>size_l2){
39             while(s){
40                 int sum=s->val+carry;
41                 s->val=sum%10;
42                 if(s->next==NULL)c=s;
43                 s=s->next;
44                 carry=sum/10;
45             }            
46         }
47         if (size_l1<size_l2){
48             while(s){
49                 int sum=s->val+carry;
50                 s->val=sum%10;
51                 if(s->next==NULL)c=s;
52                 s=s->next;
53                 carry=sum/10;
54             }            
55         }
56         if (carry) c->next=new ListNode(carry);
57         return res;
58     }
59 };

Solution2: use a dummyhead to avoid writing extra conditional statements thus simplify the code. https://leetcode.com/problems/add-two-numbers/solution/

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
12         ListNode* dummyhead=new ListNode(0);
13         ListNode* p1=l1,*p2=l2,*curr=dummyhead;
14         int carry=0;
15         while(p1||p2){
16             int x=(p1==NULL)?0:p1->val;
17             int y=(p2==NULL)?0:p2->val;
18             int sum=x+y+carry;
19             curr->next=new ListNode(sum%10);
20             carry=sum/10;
21             curr=curr->next;
22             if(p1!=NULL) p1=p1->next;
23             if(p2!=NULL) p2=p2->next;
24         }
25         if (carry) curr->next=new ListNode(carry);
26         return dummyhead->next;
27     }
28 };