2. Add Two Numbers

Intution

When adding two numbers represented as linked lists in reverse order, the least significant digits come first. This allows us to simulate the addition the same way we do manually — starting from the rightmost digits, carrying over as needed. We process both lists simultaneously, node by node, summing corresponding digits and tracking carryovers to the next digit. The final result is built as a new linked list.

Complexity

Space Complexity	Time Complexity
$\text{O}(N)$	$\text{O}(N)$

Code

public ListNode addTwoNumbers(ListNode list1, ListNode list2) {

    // Dummy node to simplify result list construction
    ListNode dummyHead = new ListNode(-1);
    ListNode currentNode = dummyHead;

    int carry = 0;  // carry from previous digit addition

    while (true) {
        // Exit condition: both lists are done and no carry remains
        if (list1 == null && list2 == null && carry == 0) break;

        // Get values from the current nodes or 0 if one list is shorter
        int digit1 = (list1 != null) ? list1.val : 0;
        int digit2 = (list2 != null) ? list2.val : 0;

        // Sum the digits and carry
        int sum = digit1 + digit2 + carry;

        // Update carry for next iteration
        carry = sum / 10;
        int digitValue = sum % 10;

        // Create a new node with the computed digit and append it to the result
        currentNode.next = new ListNode(digitValue);
        currentNode = currentNode.next;

        // Move to the next nodes in the input lists if available
        list1 = (list1 != null) ? list1.next : null;
        list2 = (list2 != null) ? list2.next : null;
    }

    // Return the next node of dummy head which points to the actual result list
    return dummyHead.next;
}