NUHMAN.com

Introduction

LeetCode’s "Add Two Numbers" problem is a classic example of working with linked lists and simulating arithmetic addition. This problem evaluates your understanding of list traversal, managing carry values, and edge cases. In this article, we’ll explore an elegant solution using Go (Golang).

Problem Statement

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.

Example

makefile

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

Understanding the Problem

Each node represents a digit, and the digits are stored in reverse. So [2,4,3] represents 342 and [5,6,4] represents 465. We add them like how we do by hand from right to left, carrying over if the sum is >= 10.

Approach

We traverse both linked lists from head to tail, simulating digit-by-digit addition:

1. Initialize a dummy head to simplify list creation.
2. Use a carry variable to store carry-over values during addition.
3. Traverse both lists, adding the digits along with the carry.
4. Create a new node with the result and move forward.
5. After traversal, if a carry remains, append a new node for it.

Go Implementation

go

package main

import (
    "fmt"
)

// Definition for singly-linked list.
type ListNode struct {
    Val  int
    Next *ListNode
}

func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    dummyHead := &ListNode{}
    current := dummyHead
    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 dummyHead.Next
}

// Helper function to create a linked list from a slice
func buildList(nums []int) *ListNode {
    dummy := &ListNode{}
    curr := dummy
    for _, val := range nums {
        curr.Next = &ListNode{Val: val}
        curr = curr.Next
    }
    return dummy.Next
}

// Helper function to print a linked list
func printList(node *ListNode) {
    for node != nil {
        fmt.Print(node.Val)
        if node.Next != nil {
            fmt.Print(" -> ")
        }
        node = node.Next
    }
    fmt.Println()
}

func main() {
    l1 := buildList([]int{2, 4, 3})
    l2 := buildList([]int{5, 6, 4})

    result := addTwoNumbers(l1, l2)
    fmt.Print("Sum: ")
    printList(result)
}

Time and Space Complexity

• Time Complexity: O(max(m, n)) — where m and n are lengths of the two lists.
• Space Complexity: O(max(m, n)) — the result list length is at most one node longer than the longest input list.

Key Points

• This problem simulates manual digit addition using a linked list structure.
• Carry-over management is key to correct implementation.
• Using a dummy node pattern helps in cleanly building the result list.