|
| 1 | +/* |
| 2 | + Given two linked lists where the nodes represent the digits of two numbers, |
| 3 | + add the numbers together and return the sum as a linked list. |
| 4 | + Ex. l1 = [2,4,3], |
| 5 | + l2 = [5,6,4] -> [7,0,8] |
| 6 | +
|
| 7 | + Traverse the linked lists and add the values of the corresponding nodes, if |
| 8 | + the sum is greater than 10, carry is present and will be added along with |
| 9 | + the next pair of digits. The lengths of the lists may differ, so check if |
| 10 | + the nodes are not null, before adding. |
| 11 | +
|
| 12 | + Time: O(max(m, n)) where m, n are lengths of l1 and l2 respectively |
| 13 | + Space: O(max(m, n)) |
| 14 | +*/ |
| 15 | + |
| 16 | +/** |
| 17 | + * Definition for singly-linked list. |
| 18 | + * struct ListNode { |
| 19 | + * int val; |
| 20 | + * struct ListNode *next; |
| 21 | + * }; |
| 22 | + */ |
| 23 | +structListNode*newNode(intval) { |
| 24 | +structListNode*node= (structListNode*)malloc(sizeof(structListNode)); |
| 25 | +node->val=val; |
| 26 | +node->next=NULL; |
| 27 | + |
| 28 | +returnnode; |
| 29 | +} |
| 30 | + |
| 31 | +structListNode*addTwoNumbers(structListNode*l1,structListNode*l2){ |
| 32 | +structListNode*head=NULL; |
| 33 | +structListNode*curr=NULL; |
| 34 | + |
| 35 | +intcarry=0; |
| 36 | + |
| 37 | +while (l1||l2) { |
| 38 | +intsum=carry; |
| 39 | + |
| 40 | +if (l1) |
| 41 | +sum+=l1->val; |
| 42 | +if (l2) |
| 43 | +sum+=l2->val; |
| 44 | + |
| 45 | +carry=sum/10; |
| 46 | +sum %=10; |
| 47 | + |
| 48 | +if (head==NULL) { |
| 49 | +head=newNode(sum); |
| 50 | +curr=head; |
| 51 | + }else { |
| 52 | +curr->next=newNode(sum); |
| 53 | +curr=curr->next; |
| 54 | + } |
| 55 | + |
| 56 | +if (l1) |
| 57 | +l1=l1->next; |
| 58 | +if (l2) |
| 59 | +l2=l2->next; |
| 60 | + } |
| 61 | + |
| 62 | +if (carry) |
| 63 | +curr->next=newNode(carry); |
| 64 | + |
| 65 | + |
| 66 | +returnhead; |
| 67 | +} |