Problem Statement

Given two non-empty linked lists representing non-negative integers, where digits are stored in reverse order and each node contains a single digit, return the sum as a linked list in the same format.

Algorithm Design

Process both lists simultaneously from head to tail, treating each position as a digit place. Maintain a running carry initialized to zero. For each iteration:

• Extract current digits from both lists, substituting zero if one list is exhausted
• Compute the total: digit from first list + digit from second list + carry
• Create a new node with value total % 10
• Update carry to total / 10
• Advance pointres in both input lists when available

Continue until both list are fully traversed and no carry remains. If a final carry exists after processing all digits, append a additional node with value 1.

Complexity Analysis

• Time Complexity: $O(\max(M, N))$, where $M$ and $N$ are the lengths of the input lists. Each node is visited exactly once.
• Space Complexity: $O(\max(M, N))$ for the output list, which stores at most $\max(M, N) + 1$ nodes.

Implementation

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

public class ReverseLinkedListAddition {
    public ListNode sumLists(ListNode headA, ListNode headB) {
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        int carry = 0;
        
        ListNode ptrA = headA;
        ListNode ptrB = headB;
        
        while (ptrA != null || ptrB != null || carry != 0) {
            int digitA = (ptrA != null) ? ptrA.val : 0;
            int digitB = (ptrB != null) ? ptrB.val : 0;
            
            int sum = digitA + digitB + carry;
            carry = sum / 10;
            int digitValue = sum % 10;
            
            current.next = new ListNode(digitValue);
            current = current.next;
            
            if (ptrA != null) ptrA = ptrA.next;
            if (ptrB != null) ptrB = ptrB.next;
        }
        
        return dummyHead.next;
    }
}

This solution utilizes a sentinel (dummy) node to streamline result construction and creates entirely new nodes for the output, leaving the original input structures unmodified.