Add Two Numbers with Linked Lists in Java: Iterative and Recursive Approaches

Introduction

A seemingly simple elementary addition problem becomes a medium‑difficulty LeetCode challenge when the numbers are stored as reversed linked lists. This guide walks through the problem, its constraints, and two practical Java solutions.

Problem Statement

You are given two non‑empty linked lists representing two non‑negative integers. Each node stores a single digit and the digits are stored in reverse order. Return the sum as a linked list in the same reverse format. You may assume the numbers do not contain leading zeros except for the number 0 itself.

ListNode Definition

public class ListNode{
    int val;
    ListNode next;
    ListNode(){}
    ListNode(int val){ this.val = val; }
    ListNode(int val, ListNode next){ this.val = val; this.next = next; }
}

Iterative Solution (Method 1)

The lists are already reversed, so we can traverse them simultaneously, adding corresponding digits along with a carry value.

class Solution{
    public ListNode addTwoNumbers(ListNode l1, ListNode l2){
        ListNode head = null, tail = null;
        int carry = 0;
        while(l1 != null || l2 != null){
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if(head == null){
                head = tail = new ListNode(sum % 10);
            }else{
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }
        if(carry > 0){
            tail.next = new ListNode(carry);
        }
        return head;
    }
}

Time complexity is O(max(m, n)) where m and n are the lengths of the two lists, because each node is visited once. Space complexity is also O(max(m, n)) for the resulting list (plus at most one extra node for a final carry).

Recursive Solution (Method 2)

The same logic can be expressed recursively, passing the carry along each call.

class Solution{
    public ListNode addTwoNumbers(ListNode l1, ListNode l2){
        return add(l1, l2, 0);
    }
    private ListNode add(ListNode l1, ListNode l2, int carry){
        if(l1 == null && l2 == null && carry == 0) return null;
        int x = (l1 == null) ? 0 : l1.val;
        int y = (l2 == null) ? 0 : l2.val;
        int sum = x + y + carry;
        ListNode node = new ListNode(sum % 10);
        node.next = add(l1 == null ? null : l1.next,
                         l2 == null ? null : l2.next,
                         sum / 10);
        return node;
    }
}

The recursive depth equals the length of the longer list (or that length plus one for a final carry), so the time complexity remains O(n). The space used by the recursion stack is also O(n), matching the size of the output list.

Conclusion

Both approaches are straightforward once the reversed‑list representation is understood. The iterative method is often clearer and avoids recursion overhead, while the recursive version showcases a clean divide‑and‑conquer style without improving asymptotic performance.