Problem Overview

When working with numerical data structures, a common algorithmic challenge involves adding two non-negative integers represented as singly linked lists. In this specific arrangement, each node stores a single digit, and the digits are stored in reverse order (least significant digit at the head). The objective is to compute the arithmetic sum and return the result as a newly constructed linked list following the same reverse-order convention.

Algorithmic Strategy

Modifying the input linked lists in-place introduces unnecessary complexity, particularly when the operands differ in length or when a final carry extends the result beyond the original maximum length. A more robust approach involves allocating a fresh linked list for the output. To streamline node attachment and eliminate special-case handling for the initial element, a sentinel (dummy) node is introduced. This placeholder sits before the actual head of the result list, allowing a uniform pointer advancement pattern throughout the traversal.

The core logic relies on a single traversal loop that continues as long as atleast one input list contains unprocessed nodes or a pending carry value exists. During each iteration, the algorithm extracts the current digit from each list (substituting zero if a list has been exhausted), computes the aggregate sum alongside the carry from the previous step, determines the new digit and updated carry, and appends a freshly allocated node to the result chain.

Implementation Details

The following Java implementation demonstrates this single-pass methodology. Variable names and control flow have been structured for clarity and optimal performance.

public class LinkedListAdder {
    public static ListNode computeSum(ListNode headA, ListNode headB) {
        ListNode sentinel = new ListNode(0);
        ListNode tail = sentinel;
        int carry = 0;

        while (headA != null || headB != null || carry != 0) {
            int operandA = (headA != null) ? headA.val : 0;
            int operandB = (headB != null) ? headB.val : 0;

            int aggregate = operandA + operandB + carry;
            carry = aggregate / 10;
            int currentDigit = aggregate % 10;

            tail.next = new ListNode(currentDigit);
            tail = tail.next;

            if (headA != null) {
                headA = headA.next;
            }
            if (headB != null) {
                headB = headB.next;
            }
        }
        return sentinel.next;
    }
}

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

Execution Flow Analysis

• Initialization: A sentinel node anchors the result list. The tail pointer tracks the most recently added node, starting at the sentinel.
• Loop Condition: The while statement evaluates three conditions simultaneously. This elegantly handles lists of unequal lengths and ensures that a leftover carry (e.g., adding 5 + 5 resulting in a new leading 1) generates an additional node without requiring post-loop cleanup logic.
• Value Extraction: Ternary operators safely retrieve node values. If a pointer has reached null, the operand defaults to 0, preventing NullPointerException and allowing the shorter list to effectively pad with zeros.
• Carry Management: Integer division (aggregate / 10) isolates the carry for the next positional column, while the modulo operator (aggregate % 10) extracts the unit digit to be stored in the new node.
• Pointer Advancement: After node creation, the tail reference shifts forward. Input pointers advance conditionally to avoid dereferencing null refreences.

Complexity Metrics

The algorithm processes each node exactly once, resulting in a time complexity of O(max(M, N)), where M and N represent the lengths of the two input linked lists. Space complexity mirrors the time complexity at O(max(M, N)) due to the allocation of the result list, which will contain either max(M, N) or max(M, N) + 1 nodes depending on whether a final carry occurs. Auxiliary space remains O(1) as only a fixed number of integer variables and pointers are utilized during computation.