Summation of linked list represented numbers.

You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

EXAMPLE

Input: (7->1->6)+(5->9->2). That is, 617+295.

Output: 2->1->9. That is, 912.

C++:
01 ListNode* addTwoNumbers2(ListNode *l1, ListNode *l2) {
02         int carry=0;
03         if((l1==NULL)||(l2==NULL))
04             return NULL;
05         int a=l1->val+l2->val;
06         if(a>9){
07             carry=1;
08             a=a10;
09         }
10         ListNode* hd=new ListNode(a);
11         ListNode* prv=hd;
12         l1=l1->next;
13         l2=l2->next;
14         while(l1&&l2){
15             int a=l1->val+l2->val+carry;
16             if(a>9){
17                 carry=1;
18                 a=a10;
19             }else
20                 carry=0;
21             ListNode* enode=new ListNode(a);
22             prv->next=enode;
23             prv=enode;
24             l1=l1->next;
25             l2=l2->next;
26         }
27         while(l1){
28             int a=l1->val+carry;
29             if(a>9){
30                 carry=1;
31                 a=a10;
32             }else
33                 carry=0;
34             ListNode* enode=new ListNode(a);
35             prv->next=enode;
36             prv=enode;
37             l1=l1->next;
38         }
39         while(l2){
40             int a=l2->val+carry;
41             if(a>9){
42                 carry=1;
43                 a=a10;
44             }else
45                 carry=0;
46             ListNode* enode=new ListNode(a);
47             prv->next=enode;
48             prv=enode;
49             l2=l2->next;
50         }
51         if(carry==1){
52             ListNode* enode=new ListNode(1);
53             prv->next=enode;
54         }
55 
56         return hd;
57 }
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