DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Add Two Numbers

#algorithms #tutorial #interview #leetcode

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

At first glance, this problem looks like simple addition.

But the catch is that the numbers are stored inside Linked Lists, and each digit is stored in reverse order.

This problem tests:

  • Linked List traversal
  • Dummy Node usage
  • Carry handling
  • Simulation of elementary addition

Let's solve it.

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.

Add the two numbers and return the sum as a linked list.

Example 

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

Output:
[7,0,8]
Enter fullscreen mode Exit fullscreen mode

Explanation:

342 + 465 = 807
Enter fullscreen mode Exit fullscreen mode

Since digits are stored in reverse order:

7 -> 0 -> 8
Enter fullscreen mode Exit fullscreen mode

Brute Force Approach

A naive approach would be:

  1. Convert both linked lists into numbers.
  2. Add them.
  3. Create a new linked list from the result.

Why Not?

This approach can fail for very large numbers because they may exceed the range of primitive data types.

Interviewers usually expect us to perform addition directly on the linked lists.

Optimal Approach

Intuition

Think exactly like elementary school addition.

For every digit:

digit1 + digit2 + carry
Enter fullscreen mode Exit fullscreen mode

Store:

sum % 10
Enter fullscreen mode Exit fullscreen mode

Carry forward:

sum / 10
Enter fullscreen mode Exit fullscreen mode

Continue until both linked lists are exhausted.

If a carry still remains, create one final node.

Why Does This Work?

Whenever the sum exceeds 9:

17
Enter fullscreen mode Exit fullscreen mode

We write:

7
Enter fullscreen mode Exit fullscreen mode

in the current position and carry:

1
Enter fullscreen mode Exit fullscreen mode

to the next position.

This is exactly how we perform addition on paper.

Dry Run

Input 

l1 = 2 -> 4 -> 3
l2 = 5 -> 6 -> 4
Enter fullscreen mode Exit fullscreen mode

Iteration 1 

2 + 5 + 0 = 7

Digit = 7
Carry = 0
Enter fullscreen mode Exit fullscreen mode

Result:

7
Enter fullscreen mode Exit fullscreen mode

Iteration 2 

4 + 6 + 0 = 10

Digit = 0
Carry = 1
Enter fullscreen mode Exit fullscreen mode

Result:

7 -> 0
Enter fullscreen mode Exit fullscreen mode

Iteration 3 

3 + 4 + 1 = 8

Digit = 8
Carry = 0
Enter fullscreen mode Exit fullscreen mode

Result:

7 -> 0 -> 8
Enter fullscreen mode Exit fullscreen mode

Final Answer 

7 -> 0 -> 8
Enter fullscreen mode Exit fullscreen mode

which represents:

807
Enter fullscreen mode Exit fullscreen mode

Optimal Java Solution 

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;

        int carry = 0;

        while (l1 != null || l2 != null) {

            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;

            int sum = x + y + carry;

            int digit = sum % 10;
            carry = sum / 10;

            cur.next = new ListNode(digit);
            cur = cur.next;

            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }

        if (carry > 0) {
            cur.next = new ListNode(carry);
        }

        return dummy.next;
    }
}
Enter fullscreen mode Exit fullscreen mode

Complexity Analysis

Metric Complexity
Time Complexity O(max(N, M))
Space Complexity O(max(N, M))

Where:

  • N = Length of first linked list
  • M = Length of second linked list

Key Interview Takeaway

The important observation is that we never need to convert the linked lists into actual numbers.

Instead, we simulate the same addition process we learned in school:

digit = sum % 10;
carry = sum / 10;
Enter fullscreen mode Exit fullscreen mode

This single idea solves the entire problem elegantly.

This problem is a reminder that many Linked List questions aren't about fancy algorithms—they're about carefully simulating a process while managing pointers correctly.

Top comments (0)