LeetCode 2: Add Two Numbers in PHP | Step-by-Step Solution

LeetCode Problem 2, Add Two Numbers, is a popular coding interview question that helps developers understand linked lists, arithmetic operations, and carry handling.

In this tutorial, we will solve the Add Two Numbers problem using PHP. We will explain the problem statement, understand linked lists, build the solution step by step, walk through a detailed dry run, and analyze the time and space complexity.

1. Problem Statement

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit.

Your task is to add the two numbers and return their sum as a linked list.

You can assume that the numbers do not contain any leading zeros, except for the number 0 itself.

Example 1

Example 2

Input:
l1 = [0]
l2 = [0]

Output:
[0]

Explanation: 0 + 0 = 0.

Example 3

Input:
l1 = [9,9,9,9,9,9,9]
l2 = [9,9,9,9]

Output:
[8,9,9,9,0,0,0,1]

Explanation: The two linked lists represent 9,999,999 and 9,999. Their sum is 10,009,998, which is returned in reverse order.

2. Understanding a Linked List

A linked list is a linear data structure in which each element is stored in a node. Each node contains a value and a reference to the next node.

Unlike an array, linked list nodes do not have to be stored in consecutive memory locations. Each node points to the next node in the sequence.

In this problem, each node contains one digit, and the digits are stored in reverse order. Therefore, [2,4,3] represents the number 342, not 243.

3. Understanding the Addition

Before writing the PHP code, let’s understand how normal addition works.

Consider adding 342 and 465:

The main idea is to process the linked lists from beginning to end, add the digits at each position, and maintain a carry for the next position.

4. Approach to Solve the Problem

We can solve this problem efficiently using a simple traversal of both linked lists and a carry variable.

• Initialize a dummy node to serve as the starting point of the result linked list.
• Maintain a pointer called current to build the result.
• Initialize carry = 0.
• Traverse both linked lists while either list has remaining nodes or a carry exists.
• Read the current digits from each list. If a list has ended, use 0 for that digit.
• Add both digits and the carry.
• Calculate the new digit using the modulo operator and update the carry using integer division.
• Create a new node for the resulting digit and append it to the result.
• Move the pointers to the next nodes and repeat until all digits and carry are processed.
• Return the next node of the dummy node as the final answer.

5. PHP Solution

LeetCode provides the ListNode class for this problem. The following is the complete solution that fits the LeetCode PHP editor.

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

        while ($l1 !== null || $l2 !== null || $carry > 0) {
            $sum = $carry;

            if ($l1 !== null) {
                $sum += $l1->val;
                $l1 = $l1->next;
            }

            if ($l2 !== null) {
                $sum += $l2->val;
                $l2 = $l2->next;
            }

            $carry = intdiv($sum, 10);
            $digit = $sum % 10;

            $current->next = new ListNode($digit);
            $current = $current->next;
        }

        return $dummy->next;
    }
}

6. Explaining the PHP Code Line by Line

Step 1: Create a Dummy Node

$dummy = new ListNode(0);
$current = $dummy;

The dummy node is an initial placeholder for the result linked list. It simplifies the process of inserting the first digit because we do not need separate logic for the first node.

The current pointer tracks the last node in the result list, allowing us to append each new digit.

Step 2: Initialize Carry

$carry = 0;

When adding two digits, their sum may be 10 or greater. The carry stores the extra value that needs to be added to the next digit position.

Step 3: Traverse Both Lists

while ($l1 !== null || $l2 !== null || $carry > 0) {
    $sum = $carry;
}

The loop continues while either linked list has a remaining node or there is a carry to process. This ensures that lists of different lengths and any final carry are handled correctly.

Step 4: Add the Current Digits

if ($l1 !== null) {
    $sum += $l1->val;
    $l1 = $l1->next;
}

if ($l2 !== null) {
    $sum += $l2->val;
    $l2 = $l2->next;
}

We add the values from both lists if the current nodes exist. If one list has ended, it contributes 0. Each pointer then advances to the next node.

Step 5: Calculate the Digit and Carry

$carry = intdiv($sum, 10);
$digit = $sum % 10;

We use intdiv() to get the integer quotient and the modulo operator to get the remainder.

• $sum % 10 gives the digit to store in the current result node.
• intdiv($sum, 10) gives the carry for the next position.

For example, if the sum is 15, the digit is 5 and the carry is 1.

Step 6: Create the Result Node

$current->next = new ListNode($digit);
$current = $current->next;

A new linked list node is created for the calculated digit and attached to the end of the result. The current pointer then advances to this newly created node.

Step 7: Return the Result

return $dummy->next;

The dummy node is only a placeholder, so we return the node after it, which is the actual head of the resulting linked list.

7. Dry Run with Example

Let’s take the input:

l1 = [2,4,3]
l2 = [5,6,4]

These linked lists represent 342 and 465 respectively.

Step 1: Add 2 and 5

2 + 5 + 0 = 7. The result digit is 7, and the carry is 0.

Step 2: Add 4 and 6

4 + 6 + 0 = 10. The result digit is 0, and the carry is 1.

Step 3: Add 3 and 4 with Carry

3 + 4 + 1 = 8. The result digit is 8, and the carry becomes 0.

The resulting linked list represents the number 807 when read in reverse order.

8. Handling Different Lengths

One linked list may contain more digits than the other. Our solution handles this by adding a digit only when its current node exists.

For example:

l1 = [9,9,9]
l2 = [1]

We calculate:

• 9 + 1 = 10 → digit 0, carry 1.
• 9 + 0 + 1 = 10 → digit 0, carry 1.
• 9 + 0 + 1 = 10 → digit 0, carry 1.
• Both lists have ended, but the carry remains 1, so we create one more node.

9. Why Do We Use a Dummy Node?

A dummy node is a temporary starting node that simplifies linked list construction. Without it, we would need special handling to initialize the head when inserting the first result digit.

Using a dummy node means every result digit can be appended using the same logic. At the end, we return $dummy->next, skipping the placeholder.

10. Time and Space Complexity

Time Complexity: O(max(n, m))

Here, n is the number of nodes in the first linked list and m is the number of nodes in the second linked list.

The algorithm traverses each linked list once and processes one digit per iteration. Therefore, the time complexity is O(max(n, m)), with at most one extra iteration for a final carry.

Space Complexity: O(max(n, m))

The result is stored in a new linked list. In the worst case, the result may have one more digit than the longer input list because of a final carry. The auxiliary space is O(1) apart from the output linked list.

11. Common Mistakes to Avoid

• Reading digits in the wrong order: The linked lists store digits in reverse order, so traverse from the head.
• Forgetting the carry: Always add the carry from the previous position to the current sum.
• Assuming both lists have the same length: Check each pointer independently and use 0 when a list has ended.
• Ignoring the final carry: The loop must continue while the carry is greater than zero.
• Returning the dummy node: Return $dummy->next, not the dummy node itself.
• Converting the full linked list into an integer: Large inputs may exceed the native integer range. Perform digit-by-digit addition instead.

12. Frequently Asked Questions

13. Conclusion

LeetCode 2: Add Two Numbers is an excellent problem for understanding linked list traversal, arithmetic operations, and carry management.

By using a dummy node, two pointers, and a carry variable, we can build the resulting linked list in a single traversal without converting the entire numbers into integers.

Practice this problem to strengthen your understanding of linked lists and prepare for technical coding interviews.