Leetcode 2: Add Two Numbers

Leetcode Link: https://leetcode.com/problems/add-two-numbers/

1. Problem Statement (Simple Explanation)

You are given two non-empty linked lists, l1 and l2, that represent two non-negative integers.

• Each node contains a single digit.

• The digits are stored in reverse order (i.e., the 1’s digit is at the head).

• You need to add the two numbers and return the sum as a linked list, also in reverse order.

You can assume:

• There are no leading zeros, except when the number itself is 0.

2. Examples

Example 1

Input:

            l1 = [2,4,3]

            l2 = [5,6,4]

        Interpreting linked lists as numbers (reverse order):

• l1 represents 342

• l2 represents 465

Output:

            [7,0,8]

Explanation:

            342+465=807

           Reversed as a list: 7 → 0 → 8.

Example 2

Input:

            l1 = [0]

            l2 = [0]

Output:

            [0]

Example 3

Input:

            l1 = [9,9,9,9,9,9,9]

            l2 = [9,9,9,9]

        Interpreted as:

• l1 = 9,999,999

• l2 = 9,999

Output:

            [8,9,9,9,0,0,0,1]

Because:

                   9,999,999+9,999=10,009,998

            Reversed digits:
            8 → 9 → 9 → 9 → 0 → 0 → 0 → 1.

3. Approach 1 – Convert to Integers (Conceptual / Not Recommended)

This is more a thought experiment than a real solution for coding interviews.

Intuition

• Convert each linked list into an integer.

• Add both integers.

• Convert the result back into a linked list.

But:

• The numbers can be very large (up to 100 digits).

• This can overflow built-in numeric types.

• Not memory or type-safe in real-world / interview constraints.

So, I mention this for understanding, but do not use it in practice.

Pseudo-code (Conceptual Only)

Here’s what the three functions do:

• listToNumber(list) converts a linked list where each node holds a single digit (least significant digit first) into an integer. It walks the list, accumulating num by multiplying each digit by an increasing multiplier (1, 10, 100, …).

• numberToList(num) converts an integer back into a linked list in the same format (least significant digit first). It repeatedly takes num % 10 to get the current digit, creates a node for it, and divides num by 10 until num becomes 0. A dummy head simplifies construction.

• addTwoNumbers(l1, l2) adds two numbers represented by such linked lists by:

  1. Converting both lists to integers (n1, n2),
  2. Summing them,
  3. Converting the sum back to a linked list.

Complexity after Ignoring overflow:

• Time: O(m+n+k) (m, n are lengths of lists, k is number of digits of sum).

• Space: O(k).

But again: not acceptable due to overflow risk.

4. Approach 2 – Digit-by-Digit Addition with Carry (Optimal)

This is the standard, safe, and interview-approved solution.

Intuition

This mimics how you do addition by hand, from right to left:

• Add digits at the same position plus any carry from the previous position.

• Store sum % 10 as the current node.

• Carry sum / 10 (integer division) to the next position.

Since the lists are already in reverse order, their head nodes are the least significant digits, making it easy to add from left to right.

Algorithm (Step-by-Step)

Let l1 and l2 be the head nodes of the two lists.

1. Initialize:

• carry = 0

• Create a dummy node to simplify list building.

• current = dummy.

2. While at least one of l1 or l2 is not null, or carry > 0:

• Let:

• x = l1.val if l1 is not null, else 0

• y = l2.val if l2 is not null, else 0

• Compute:

• sum = x + y + carry

• digit = sum % 10

• carry = sum / 10 (integer division)

• Create a new node with digit and attach it to current.next.

• Move current to current.next.

• Move l1 and l2 to their next nodes if they are not null.

3. After the loop, dummy.next is the head of the resulting linked list.

Pseudo-code (Optimized)

This function adds two numbers represented by linked lists where each node stores a single digit, with the least significant digit first. It uses a dummy head to simplify list construction and a current pointer to append result nodes. A carry variable tracks overflow from digit addition.

In each iteration of the loop—while either list has nodes or there’s a carry—it reads the current digits x and y (using 0 if a list has ended). It computes sum = x + y + carry, extracts the result digit as sum % 10, and updates carry = sum // 10. A new node with the digit is appended to the result, and the pointers l1 and l2 advance if possible.

When both lists are exhausted, any remaining carry (e.g., 1 after adding 9 + 1) is handled by the loop condition and becomes an extra node. Time complexity: O(max(m, n)). Space (output): proportional to the number of digits in the sum. This approach avoids integer overflow and works for arbitrarily large inputs.

Time and Space Complexity

Let:

• m = length of l1

• n = length of l2

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

We process each node once.

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

for the output list (we must store the result). Extra variables are constant.

Java code:

This method adds two numbers represented by singly linked lists where each node contains one digit and the least significant digit comes first (reverse order). It uses a dummy head (dummy) to simplify building the result list and a current pointer to append new nodes. A carry integer tracks overflow from digit addition.

The loop runs while at least one list still has nodes or there’s a nonzero carry. In each iteration, it reads the current digits x and y (using 0 if a list is exhausted), computes sum = x + y + carry, derives the resulting digit with sum % 10, and updates carry = sum / 10. It then creates a new node with the digit and advances current. Pointers l1 and l2 move forward when available.

When both lists end, any remaining carry (e.g., 1 from 9+1) is handled by the loop condition and becomes an extra node.

C code:

This C code adds two non-negative integers represented as singly linked lists, where each node stores one digit in reverse order (least significant digit first).

• ListNode defines the node structure (val and next).
• createNode(int val) allocates and initializes a new node with the given digit.
• addTwoNumbers(l1, l2) performs the addition:
  • It uses a dummy head (dummy) to simplify list construction and a current pointer to append new result nodes.
  • A carry variable accumulates overflow from digit sums.
  • The while loop continues as long as there are remaining nodes in l1 or l2, or a non-zero carry.
  • For each step, it reads digits x and y (0 if a list is exhausted), computes sum = x + y + carry, extracts the new digit digit = sum % 10, and updates carry = sum / 10.
  • It creates a node for digit and advances list pointers.

Finally, it returns dummy.next, the head of the summed list.

C++ code:

This code adds two non‑negative integers stored as singly linked lists in reverse order (least significant digit first). The Solution::addTwoNumbers method uses a dummy head node (dummy) to simplify building the result list and a current pointer to append new nodes. A carry variable tracks overflow between digit additions.

In each loop iteration, it reads the current digits x and y from l1 and l2 (using 0 if a list is exhausted), computes sum = x + y + carry, extracts the result digit with sum % 10, and updates carry = sum / 10. It then creates a new node (new ListNode(digit)) and advances current. Pointers l1 and l2 move forward when not null. The loop continues while there are digits left or a nonzero carry, ensuring cases like an extra final carry (e.g., 999 + 1) are handled. Finally, it returns dummy.next, the head of the summed list.

Python code:

This function adds two non‑negative integers represented as singly linked lists in reverse order (least significant digit first). It uses a dummy head node (dummy) to simplify building the result list and a current pointer to append new nodes. A carry variable tracks overflow between digit additions.

Inside the while loop, it reads x and y from l1 and l2 (0 if a list is exhausted), computes s = x + y + carry, extracts the resulting digit with s % 10, and updates carry = s // 10. It creates a new node with digit, advances current, and moves l1/l2 forward when available. The loop continues while there are nodes left or a nonzero carry, ensuring cases like a final carry (e.g., 999 + 1 → an extra node) are handled.

JavaScript code:

This function adds two non‑negative integers represented as singly linked lists in reverse order (least significant digit first). It uses a dummy head node (dummy) to simplify constructing the result list and a current pointer to append new nodes as digits are computed. A carry variable preserves overflow between additions.

Inside the while loop, it reads the current digits x and y from l1 and l2 (or 0 if a list has ended). It computes sum = x + y + carry, extracts the new digit with sum % 10, and updates carry = Math.floor(sum / 10) for the next iteration. A new node with digit is appended (current.next = new ListNode(digit)), and current advances. Pointers l1 and l2 move forward when not null. The loop continues while any list has nodes left or there’s a nonzero carry, correctly handling cases like a final carry (e.g., 999 + 1).

Finally, the summed list’s head is dummy.next.