# 02 Add Two Numbers

### Description

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 contains a single digit. Add the two numbers and return the sum as a linked list.

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

Add Two Numbers - LeetCode

### Simple Solution

This problem is actually relatively simple as long as I am pretty familiar with linked list (not with c++ grammar however, which is necessary for me to catch up). Just set up one carrier bit, and then add up digits one by one. Sort like merging two sorted arrays.

### Code

class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
int carrier = 0;
ListNode* answer = new ListNode;
ListNode* ans = answer;

while (l1 != NULL && l2 != NULL) {
ans->val = (l1->val + l2->val + carrier) % 10;
carrier = (l1->val + l2->val + carrier) / 10;

if (l1->next != NULL || l2->next != NULL) {
ListNode* newNode = new ListNode;
ans = ans->next = newNode;
}
l1 = l1->next;
l2 = l2->next;
}

while (l1 != NULL) {
ans->val = (l1->val + carrier) % 10;
carrier = (l1->val + carrier) / 10;

if (l1->next != NULL) {
ListNode* newNode = new ListNode;
ans = ans->next = newNode;
}
l1 = l1->next;
}

while (l2 != NULL) {
ans->val = (l2->val + carrier) % 10;
carrier = (l2->val + carrier) / 10;

if (l2->next != NULL) {
ListNode* newNode = new ListNode;
ans = ans->next = newNode;
}
l2 = l2->next;
}

if (carrier != 0) {
ListNode* newNode = new ListNode;
ans = ans->next = newNode;
ans->val = carrier;
}

}
};


### Complexity Analysis

Time complexity

This code need and only need one way look up. As a result, the time complexity is $O(n)$.

Space complexity

Only one linked list is need and one carrier int. So space complexity is also $O(n)$. ##### penway Wang
###### Mechanic Technical Director

My research interests include computer vision, artificial intelligence and software engineering. I am a FSAE race car crew member at the same time, designing suspension system.