# 445. Add Two Numbers II

## LeetCode [445. Add Two Numbers II](https://leetcode-cn.com/problems/add-two-numbers-ii/)

### Description

You are given two **non-empty** linked lists representing two non-negative integers. The most significant digit comes first 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.

**Follow up:**\
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

**Example:**

```
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
```

### Tags

Linked List

### Solution

We add up the values of the two nodes from both linked lists that correspond to each other in position from tail to head recursively. Before enter the recursion, we compute the lengths of given linked lists, as well as the difference of both, denoted as `delta`. Initialize 2 pointers `long` and `short`, and assign them to the head of longer list and shorter one respectively.

The recursion boundary is `long` is null. We initialize a new node and then check if `delta == 0`. If `delta` is not zero, it means that we are processing higher bits of the sum. Thus, the value of the current node is `long.Val`, and the point `Next` to `recursion(long.Next, short, delta-1)`, which means the `long` moves 1 step forward and their difference gets decreaced by 1. Otherwise, we are dealing with the lower bits of the sum, adding up `long.Val` and `short.Val` as the current node's value, and point `Next` to `recursion(long.Next, short.Next, 0)`, i.e. move both pointers 1 step forward and there are no difference between them.

After building the current node, we need to evaluate the carry from the next node. In other words, if the value of the next node `curNode.Next.Val` is larger than 10, the carry `curNode.Next.Val / 10` should be added to its higher unit `curNode.Val`, and `curNode.Next.Val` is retained in single digit only.

### Complexity

* Time complexity: $$O(n)$$; `n` is the length of the longer input list.
* Space complexity: $$O(n)$$ for new list.

### Code

```go
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	var head *ListNode
	len1, len2 := getLength(l1), getLength(l2)
	if len1 > len2 {
		head = recursion(l1, l2, len1-len2)
	} else {
		head = recursion(l2, l1, len2-len1)
	}
	if head != nil && head.Val > 9 {
		temp := &ListNode{head.Val / 10, head}
		head.Val %= 10
		head = temp
	}
	return head
}

func recursion(long, short *ListNode, delta int) *ListNode {
	if long == nil {
		return nil
	}
	curNode := &ListNode{}
	if delta == 0 {
		curNode.Val = long.Val + short.Val
		curNode.Next = recursion(long.Next, short.Next, 0)
	} else {
		curNode.Val = long.Val
		curNode.Next = recursion(long.Next, short, delta-1)
	}
	if curNode.Next != nil && curNode.Next.Val > 9 {
		curNode.Val += curNode.Next.Val / 10
		curNode.Next.Val %= 10
	}
	return curNode
}

func getLength(head *ListNode) int {
	var l int
	for p := head; p != nil; p = p.Next {
		l++
	}
	return l
}
```