Interview question + solution

add-two-numbers.go

/*
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 contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:
• The number of nodes in each linked list is in the range [1, 100]
• 0 <= node.value <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.
*/

package main

import "fmt"

type Node struct {
	val  int
	next *Node
}

const Base int = 10

func reverse(n *Node) *Node {
	var prev *Node = nil
	var temp *Node
	for n != nil {
		temp = n.next
		n.next = prev
		prev = n
		n = temp
	}
	return prev
}

func add(x *Node, y *Node) *Node {
	if x == nil {
		return y
	}
	if y == nil {
		return x
	}

	carry := 0
	var head *Node
	var curr *Node

	for x != nil || y != nil {
		if x != nil {
			carry += x.val
			x = x.next
		}
		if y != nil {
			carry += y.val
			y = y.next
		}
		z := &Node{
			val:  carry % Base,
			next: nil,
		}
		if head != nil {
			curr.next = z
			curr = z
		} else {
			head = z
			curr = z
		}
		carry /= Base
	}

	if carry != 0 {
		z := &Node{
			val:  carry,
			next: nil,
		}
		curr.next = z
	}

	return head
}

func main() {
	x := &Node{
		val: 8,
		next: &Node{
			val: 5,
			next: &Node{
				val:  9,
				next: nil,
			},
		},
	}

	y := &Node{
		val: 7,
		next: &Node{
			val: 6,
			next: &Node{
				val: 6,
				next: &Node{
					val:  3,
					next: nil,
				},
			},
		},
	}

	z := add(x, y)

	for z != nil {
		fmt.Println(z.val)
		z = z.next
	}
}