Solving LeetCode’s “Add Two Numbers” Problem in Kotlin: A Complete Guide

The “Add Two Numbers” problem on LeetCode is a classic linked list manipulation problem that comes up a lot in job interviews. This problem will test how well you understand linked lists, how to handle carries, and how to deal with edge cases. In this article, we’ll look at several Kotlin solutions and explain them in detail, as well as look at their level of difficulty.

What the Problem Is

You have two linked lists that are not empty and represent two non-negative integers. The numbers are stored in reverse order, and each node has only one digit. Add the two numbers together and give back the sum as a linked list.

You can assume that the two numbers don’t have any leading zeros, except for the number 0 itself.

ListNode representation

class ListNode(var `val`: Int) {
    var next: ListNode? = null
}

Examples

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.val ≤ 9
• It is guaranteed that the list represents a number that does not have leading zeros

Why is “Add Two Numbers” Popular in Interviews?

The Add Two Numbers problem (LeetCode #2) may look deceptively simple, but it tests a candidate’s ability to implement linked list manipulation, carry propagation, and iterative vs. recursive reasoning   all staple skills in coding interviews.

Many top-tier companies have used this exact problem or its variants in their interviews, including:

• Amazon
• Microsoft
• Google
• Bloomberg
• Meta (Facebook)
• Apple

This highlights its relevance for candidates preparing for competitive roles at FAANG and finance firms alike.

Unlike array-based problems that emphasise index manipulation, Add Two Numbers forces interviewees to think in terms of node-based data structures, edge cases (like adding 9999 + 1), and potential trade-offs between iterative and recursive approaches. This is the reason companies continue to ask this question years after its introduction.

Keep in mind: Mastering this problem not only prepares you for algorithmic coding tests but also signals comfort with low-level pointer handling, data structure fundamentals, and writing clean, bug-free logic under time pressure   traits that interviewers value highly.

Solution 1: Iterative Approach with Carry Handling

This is the most straightforward and commonly used approach. We iterate through both linked lists simultaneously, adding corresponding digits along with any carryover from the previous addition.

class Solution {
    fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
        val dummy = ListNode(0)
        var current = dummy
        var carry = 0
        var p1 = l1
        var p2 = l2
        
        while (p1 != null || p2 != null || carry != 0) {
            val x = p1?.`val` ?: 0
            val y = p2?.`val` ?: 0
            val sum = carry + x + y
            
            carry = sum / 10
            current.next = ListNode(sum % 10)
            current = current.next!!
            
            p1 = p1?.next
            p2 = p2?.next
        }
        
        return dummy.next
    }
}

How It Works

1. Initialize: Create a dummy node to simplify list construction and track carry
2. Iterate: Process both lists simultaneously until both are exhausted and no carry remains
3. Calculate: For each position, add the digits from both lists plus any carry
4. Update: Set the new carry and create a node with the digit (sum % 10)
5. Advance: Move to the next nodes in both lists

Time and Space Complexity

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

Solution 2: Recursive Approach

This elegant solution uses recursion to handle the addition, making the code more concise and easier to understand for those familiar with recursive thinking.

class Solution {
    fun addTwoNumbers(l1: ListNode?, l2: ListNode?, carry: Int = 0): ListNode? {
        // Base case: both lists are null and no carry
        if (l1 == null && l2 == null && carry == 0) {
            return null
        }
        
        val sum = carry + (l1?.`val` ?: 0) + (l2?.`val` ?: 0)
        val result = ListNode(sum % 10)
        
        result.next = addTwoNumbers(l1?.next, l2?.next, sum / 10)
        return result
    }
}

How It Works

1. Base Case: Return null when both lists are exhausted and no carry remains
2. Calculate: Add current digits and carry
3. Create Node: Make a new node with the digit value
4. Recurse: Call the function recursively for the next nodes with the new carry

Time and Space Complexity

• Time Complexity: O(max(m, n))
• Space Complexity: O(max(m, n)) due to recursion stack and result list

Solution 3: Functional Kotlin Approach

Leveraging Kotlin’s functional programming features, we can create a more idiomatic solution:

class Solution {
    fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
        fun addWithCarry(node1: ListNode?, node2: ListNode?, carry: Int): ListNode? {
            if (node1 == null && node2 == null && carry == 0) return null
            
            val sum = (node1?.`val` ?: 0) + (node2?.`val` ?: 0) + carry
            return ListNode(sum % 10).apply {
                next = addWithCarry(node1?.next, node2?.next, sum / 10)
            }
        }
        
        return addWithCarry(l1, l2, 0)
    }
}

This approach utilises Kotlin’s scope function to create more concise code while preserving readability.

Solution 4: Tail-Recursive Optimization

For better performance with large inputs, we can use tail recursion:

class Solution {
    fun addTwoNumbers(l1: ListNode?, l2: ListNode?): ListNode? {
        val dummy = ListNode(0)
        
        tailrec fun addNodes(
            node1: ListNode?, 
            node2: ListNode?, 
            carry: Int, 
            current: ListNode
        ) {
            if (node1 == null && node2 == null && carry == 0) return
            
            val sum = (node1?.`val` ?: 0) + (node2?.`val` ?: 0) + carry
            current.next = ListNode(sum % 10)
            
            addNodes(node1?.next, node2?.next, sum / 10, current.next!!)
        }
        
        addNodes(l1, l2, 0, dummy)
        return dummy.next
    }
}

Edge Cases to Consider

When implementing this solution, ensure that it handles these edge cases:

1. Different length lists: [99] + [9] = [8, 0, 1]
2. Carry at the end: [5] + [5] = [0,1]
3. Single digit: [0] + [0] = [0]
4. Multiple carries: [9,9,9] + [9,9,9] = [8,9,9,1]

Testing Your Solution

Here’s a comprehensive test suite in Kotlin:

fun main() {
    val solution = Solution()
    
    // Test case 1: [2,4,3] + [5,6,4] = [7,0,8]
    val l1 = ListNode(2).apply {
        next = ListNode(4).apply {
            next = ListNode(3)
        }
    }
    val l2 = ListNode(5).apply {
        next = ListNode(6).apply {
            next = ListNode(4)
        }
    }
    
    val result = solution.addTwoNumbers(l1, l2)
    printList(result) // Should print: 7 -> 0 -> 8
    
    // Add more test cases...
}

fun printList(head: ListNode?) {
    var current = head
    val values = mutableListOf<Int>()
    while (current != null) {
        values.add(current.`val`)
        current = current.next
    }
    println(values.joinToString(" -> "))
}

Key Takeaways

1. Understand the Problem: The digits are stored in reverse order, which simplifies addition
2. Handle Carry Properly: Don’t forget to check for carry after processing both lists
3. Use Dummy Nodes: They simplify linked list construction
4. Consider Edge Cases: Test with different list lengths and carry scenarios
5. Choose the Right Approach: Iterative is generally preferred for its simplicity and efficiency

Table comparison of solutions

| Approach        | Time Complexity | Space Complexity | Pros              | Cons                |
|-----------------|----------------|------------------|--------------------|---------------------|
| Iterative       | O(max(m,n))    | O(max(m,n))      | Simple, efficient  | More verbose        |
| Recursive       | O(max(m,n))    | O(max(m,n))      | Elegant, concise   | Stack overflow risk |
| Functional      | O(max(m,n))    | O(max(m,n))      | Idiomatic Kotlin   | May be less familiar|
| Tail-Recursive  | O(max(m,n))    | O(max(m,n))      | Stack-safe         | More complex        |

Beyond the code

The “Add Two Numbers” problem is an excellent introduction to linked list manipulation and carry handling. The iterative approach is generally recommended for its simplicity and efficiency, but understanding the recursive solution helps develop problem-solving skills.

When solving similar problems, remember to:

• Draw out examples to understand the pattern
• Handle edge cases. systematically
• Test with various input sizes
• Consider both time and space complexity

The LeetCode Community’s answers and discussions, along with other programming resources, served as inspiration for this article. Work on your algorithmic thinking by doing this problem and other linked list problems that are similar.

Link to this same article in my personal blog

Happy coding!

David Cruz
davthecoder.com paglipat.com