Problem Description

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node 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.

Examples

Example 1:

Input: list1 = [2,4,3], list2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807

Example 2:

Input: list1 = [0], list2 = [0]
Output: [0]

Example 3:

Input: list1 = [9,9,9,9,9,9,9], list2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Iterative Solution Approach

Traverse both linked lists simultaneously, simulating the addition process digit by digit. Handle cases where lists have different lengths by treating missing nodes as zeros. Maintain a carry value when the sum of digits exceeds 9.

Go Implementation - Iterative Method

type ListNode struct {
    Value int
    Next  *ListNode
}

func addLinkedNumbers(num1 *ListNode, num2 *ListNode) *ListNode {
    resultHead := &ListNode{Value: 0}
    current := resultHead
    carry := 0
    
    for num1 != nil || num2 != nil {
        digit1, digit2 := 0, 0
        
        if num1 != nil {
            digit1 = num1.Value
            num1 = num1.Next
        }
        
        if num2 != nil {
            digit2 = num2.Value
            num2 = num2.Next
        }
        
        total := carry + digit1 + digit2
        carry = total / 10
        current.Next = &ListNode{Value: total % 10}
        current = current.Next
    }
    
    if carry > 0 {
        current.Next = &ListNode{Value: carry}
    }
    
    return resultHead.Next
}

Algorithm Analysis

• Time Complexity: O(max(m, n)) where m and n are the lengths of the two linked lists
• Space Complexity: O(max(m, n)) for the resulting linked list

Alternative Implementation - Direct Simulation

This approach directly simulates the addition process by processing each node pair and handling carry propagation.

Go Implementation - Simulation Method

func computeListSum(first *ListNode, second *ListNode) *ListNode {
    dummy := &ListNode{Value: 0}
    current := dummy
    remainder := 0
    
    for first != nil || second != nil || remainder > 0 {
        total := remainder
        
        if first != nil {
            total += first.Value
            first = first.Next
        }
        
        if second != nil {
            total += second.Value
            second = second.Next
        }
        
        remainder = total / 10
        current.Next = &ListNode{Value: total % 10}
        current = current.Next
    }
    
    return dummy.Next
}

Algorithm Analysis

• Time Complexity: O(max(m, n))
• Space Complexity: O(max(m, n))

Solution Approaches Comparison

The iterative and simulation methods are fundamentally similar in appproach and complexity. Both methods process nodes sequentialy while maintaining carry information. The primary differences lie in code organization and variable naming.

Key considerations for this problem:

• Handle different list lengths gracefully
• Properly manage carry propagation
• Create new nodes for the result list
• Edge case: final carry after processing all node

While recursive solutions exist, they offer no complexity advantages and may cause stack overflow for long lists. The iterative approaches provide optimal time and space complexity for this problem.