# 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
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://txfs19260817.gitbook.io/leetcode-go-notes/solutions/445.-add-two-numbers-ii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.