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

C++:
01 /**
02  * Definition for singly-linked list.
03  * struct ListNode {
04  *     int val;
05  *     ListNode *next;
06  *     ListNode(int x) : val(x), next(NULL) {}
07  * };
08  */
09 class Solution {
10 public:
11     ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
12         // Start typing your C/C++ solution below
13         // DO NOT write int main() function
14         int carry=0;
15         ListNode* p=l1;
16         ListNode* q=l2;
17         ListNode* result=NULL;
18         ListNode* end=NULL;
19         while((p!=NULL)&&(q!=NULL))
20         {
21             int t=p->val+q->val+carry;
22             p=p->next;
23             q=q->next;
24             if(t>=10)
25             {
26                 carry=1;
27                 t=t10;
28             }
29             else
30             {
31                 carry=0;
32             }
33             ListNode* item=new ListNode(t);
34             if(end!=NULL)
35             {
36                 end->next=item;
37                 end=item;
38             }
39             else
40             {
41                 result=item;
42                 end=item;
43             }
44         }
45         while((p!=NULL)||(q!=NULL))
46         {
47             int t=0;
48             if(p!=NULL)
49             {
50                 t=p->val+carry;
51                 p=p->next;
52             }
53             if(q!=NULL)
54             {
55                 t=q->val+carry;
56                 q=q->next;
57             }
58             if(t>=10)
59             {
60                 carry=1;
61                 t=t10;
62             }
63             else
64             {
65                 carry=0;
66             }
67             ListNode* item=new ListNode(t);
68             if(end!=NULL)
69             {
70                 end->next=item;
71                 end=item;
72             }
73             else
74             {
75                 result=item;
76                 end=item;
77             }
78         }
79         if(carry==1)
80         {
81             ListNode* item=new ListNode(1);
82             if(end!=NULL)
83             {
84                 end->next=item;
85                 end=item;
86             }
87             else
88             {
89                 result=item;
90                 end=item;
91             }
92         }
93         return result;
94     }
95 };
Advertisements
This entry was posted in Array and linked list. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s