LeetCode Go #2. Add Two Numbers

Problem Description

You can find the problem on Leetcode.

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.

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]

Understand Problem

We are given two linked lists representing non-negative integers. The digits are stored in reverse order, meaning the units digit is at the head of the list. We need to add the two numbers and return the result as a new linked list.

Implementation

Let's implement the solution in Go.

package main

type ListNode struct {
    Val  int
    Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    curr := dummyHead
    carry := 0

    for l1 != nil || l2 != nil {
        sum := carry

        if l1 != nil {
            sum += l1.Val
            l1 = l1.Next
        }

        if l2 != nil {
            sum += l2.Val
            l2 = l2.Next
        }

        curr.Next = &ListNode{Val: sum % 10}
        curr = curr.Next
        carry = sum / 10
    }

    if carry > 0 {
        curr.Next = &ListNode{Val: carry}
    }

    return dummyHead.Next
}

Testing

Let's write some tests to verify that our implementation is correct.

package main

import (
    "reflect"
    "testing"
)

func buildLinkedList(nums []int) *ListNode {
    dummyHead := &ListNode{}
    curr := dummyHead

    for _, num := range nums {
        curr.Next = &ListNode{Val: num}
        curr = curr.Next
    }

    return dummyHead.Next
}

func getListValues(head *ListNode) []int {
    values := make([]int, 0)

    for head != nil {
        values = append(values, head.Val)
        head = head.Next
    }

    return values
}

func TestAddTwoNumbers(t *testing.T) {
    tests := []struct {
        l1   []int
        l2   []int
        want []int
    }{
        {[]int{2, 4, 3}, []int{5, 6, 4}, []int{7, 0, 8}},
        {[]int{0}, []int{0}, []int{0}},
        {[]int{9, 9, 9, 9, 9, 9, 9}, []int{9, 9, 9, 9}, []int{8, 9, 9, 9, 0, 0, 0, 1}},
    }

    for _, test := range tests {
        l1 := buildLinkedList(test.l1)
        l2 := buildLinkedList(test.l2)
        got := getListValues(addTwoNumbers(l1, l2))

        if !reflect.DeepEqual(got, test.want) {
            t.Errorf("Input: l1=%v, l2=%v\nGot: %v\nWant: %v", test.l1, test.l2, got, test.want)
        }
    }
}

Conclusion

Well done! You have successfully solved the Add Two Numbers problem on Leetcode. This problem introduced you to arithmetic operations on linked lists. By reversing the order of digits, you were able to perform addition on the linked lists and return the result as a new linked list.

Now that you have gained confidence in solving this problem, it's time to tackle more challenges on Leetcode. Keep practicing and enhancing your problem-solving skills. Good luck with your future endeavors!