# Add two numbers represented by linked lists

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.

Example 1:

```
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.
```

Example 2:

```
Input: l1 = [0], l2 = [0]
Output: [0]
```

Example 3:

```
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]
```

**c++ implementation:**

struct Node* addTwoLists(struct Node* l1, struct Node* l2) { Node* head=new Node(1); Node* temp=head; int carry=0; while(l1!=NULL || l2!=NULL || carry) { int sum=0; if(l1!=NULL) { sum=sum+l1->data; l1=l1->next; } if(l2!=NULL) { sum=sum+l2->data; l2=l2->next; } sum=sum+carry; carry=sum/10; Node* node=new Node(sum%10); temp->next=node; temp=temp->next; } return head->next; }

Time Complexity: O(N+M)

Space Complexity: O(Max(N,M))

Space Complexity: O(Max(N,M))