LeetCode #2 Add Two Numbers

Medium

Problem

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

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

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution

Traverse two lists at the same time and use a carry bit to save carry. Once one list reaches end, let another one deals with carry. It’s noted that we should remember to handle last carry after leaving iteration.

Complexity

Let m and n denote to amount of nodes in these two list. Because we only traverse each list once, time complexity of this method is only O(m+n).

Because we restore results in l1 and only allocate one new node if there is a carry after leaving iteration, it only uses O(1) extra space.