Add Two Numbers: Navigating Linked Lists in Coding Interview

Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

For instance, given (2 -> 4 -> 3) and (5 -> 6 -> 4), you should return (7 -> 0 -> 8), representing the number 807.

Intuition

Think of the process of elementary school addition. We learned to add numbers from right to left, carrying over any value greater than 9 to the next left position. This problem is the same! But instead of a sequence of digits, you’re using nodes in a linked list.

Imagine two stacks of toy blocks. Each block has a number (0-9) written on it. You’re trying to stack them on top of each other, and if the sum exceeds 9, you place the remainder and remember to add 1 to the next stack.

Brute Force Solution

A naive approach might involve converting each linked list to a number, adding the two numbers, and then converting the resultant number back to a linked list. However, this approach can be problematic for very long linked lists as the number might exceed standard data type limits.

// Definition for singly-linked list.
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; }
}

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        long num1 = convertListToNumber(l1);
        long num2 = convertListToNumber(l2);
        return convertNumberToList(num1 + num2);
    }

    public long convertListToNumber(ListNode node) {
        long num = 0, multiplier = 1;
        while (node != null) {
            num += node.val * multiplier;
            multiplier *= 10;
            node = node.next;
        }
        return num;
    }

    public ListNode convertNumberToList(long num) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        do {
            current.next = new ListNode((int)(num % 10));
            num /= 10;
            current = current.next;
        } while (num > 0);
        return dummy.next;
    }
}

Optimal Solution

A better approach is to simulate the addition from right to left just as we do for regular number addition.

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;

        // While there are still digits in either list or a carry
        while (l1 != null || l2 != null || carry != 0) {
            int sum = carry;
            if (l1 != null) {
                sum += l1.val;
                l1 = l1.next;
            }
            if (l2 != null) {
                sum += l2.val;
                l2 = l2.next;
            }

            // Calculate carry for next calulation
            carry = sum / 10;
            // Create a new node with the remainder
            current.next = new ListNode(sum % 10);
            current = current.next;
        }

        return dummy.next;
    }
}

In the above code:

1. We start with a dummy node to make handling the result list easier.
2. We iterate while either of the linked lists is not exhausted or we still have a carry from a previous addition.
3. For each iteration, we add the corresponding values from l1 and l2 (if they exist) and the carry from the last iteration.
4. We then calculate the new carry (if any) and append a new node to our result list with the remainder of our sum.
5. Once we’re done iterating, we return the list starting from the next node of our dummy to exclude the dummy.