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.
```

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

```## Blog link: https://code.dennyzhang.com/add-two-numbers
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
## Idea:
##         Need to track the previous node
##         Take in-place change? Empty links?
## Complexity: Time O(n), Space O(1)
## Sample Data:
##  2 -> 4 -> 3
##  p    r
##  5 -> 6 -> 8 -> 9
##  q    s
##  One or two link are empty
if l1 is None or l2 is None:
return l1 if l2 is None else l2

has_carry = False
p, q = l1, l2
r, s = p.next, q.next
p.val += q.val

if p.val >= 10:
p.val = p.val % 10
has_carry = True

# merge 2 list
while r and s:
if has_carry is True:
r.val += 1
has_carry = False
r.val += s.val
if r.val >= 10:
has_carry = True
r.val = r.val % 10
p, q = p.next, q.next
r, s = p.next, q.next

# If reach the end of one list
if q.next:
p.next = q.next
r = p.next

# Merge the remaining
while r:
if has_carry is True:
r.val += 1
has_carry = False
if r.val >= 10:
has_carry = True
r.val = r.val % 10
p = p.next
r = p.next

# If has_carry in the end
if has_carry is True:
tmp_node = ListNode(1)
p.next = tmp_node