445. Add Two Numbers II

LeetCode 445. 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

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
}