Add Two Numbers

linked-list • math
Medium

You are given two non-empty linked lists representing two non-negative integers. Add the two numbers and return the sum as a linked list.

Examples

Input
l1 = [2,4,3], l2 = [5,6,4]
Output
[7,0,8]
342 + 465 = 807 -> [7,0,8]
Input
l1 = [0], l2 = [0]
Output
[0]
0 + 0 = 0

Solution

Traverse both lists simultaneously, add corresponding digits plus carry.
Create new nodes for the resulting digits and propagate carry to the next position.
Time: O(max(m,n))O(max(m,n)), Space: O(max(m,n))O(max(m,n)) for the result list.

Code Solution

add-two-numbers.cpp
cpp
1
#include <iostream>
2
#include <vector>
3
using namespace std;
4


5
struct ListNode { int val; ListNode* next; ListNode(int x): val(x), next(nullptr) {} };
6


7
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
8
  ListNode dummy(0);
9
  ListNode* p = &dummy;
10
  int carry = 0;
11
  while (l1 || l2 || carry) {
12
    int sum = carry;
13
    if (l1) { sum += l1->val; l1 = l1->next; }
14
    if (l2) { sum += l2->val; l2 = l2->next; }
15
    carry = sum / 10;
16
    p->next = new ListNode(sum % 10);
17
    p = p->next;
18
  }
19
  return dummy.next;
20
}