Solving the LeetCode "Add Two Numbers" Problem in Go

Difficulty: Medium | Tags: Linked List, Math, Recursion

Introduction

The "Add Two Numbers" problem requires adding two numbers represented as linked lists in reverse order. This is a fundamental problem for understanding linked list manipulation and arithmetic operations in data structures.

Problem Analysis

Given two non-empty linked lists, each node contains a single digit of a non-negative integer stored in reverse order. The task is to add these two numbers and return the result as a linked list in the same reverse order. For example, adding [2,4,3] (342) and [5,6,4] (465) results in [7,0,8] (807).

Solution Approach

The solution involves traversing both linked lists simultaneously, adding corresponding digits along with any carry from the previous addition. The result is built digit by digit, and the carry is propagated until both lists are exhausted. A dummy node simplifies the construction of the result list.

Go Implementation

/**
* Definition for singly-linked list.
* type ListNode struct {
    *     Val int
    *     Next *ListNode
    * }
    */
    func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
        dummy := &ListNode{}
        current := dummy
        carry := 0
        for l1 != nil || l2 != nil || carry != 0 {
            sum := carry
            if l1 != nil {
                sum += l1.Val
                l1 = l1.Next
            }
            if l2 != nil {
                sum += l2.Val
                l2 = l2.Next
            }
            carry = sum / 10
            current.Next = &ListNode{Val: sum % 10}
            current = current.Next
        }
        return dummy.Next
    }

Complexity Analysis

Time Complexity: O(max(n, m)), where n and m are the lengths of the two linked lists. We traverse each list once.

Space Complexity: O(max(n, m)), the result list's length is at most max(n, m) + 1 due to a potential carry.

Testing and Examples

Test cases include:

• Adding [2,4,3] and [5,6,4] → [7,0,8]
• Adding [0] and [0] → [0]
• Adding [9,9,9,9,9,9,9] and [9,9,9,9] → [8,9,9,9,0,0,0,1]

Best Practices and Tips

Key takeaways:

• Use a dummy node to simplify list construction.
• Handle carry propagation carefully, especially when lists are exhausted.
• Edge cases include lists of unequal lengths and a final carry.