Adding Two Numbers Represented by Linked Lists

Introduction

In this problem, two non-negative integers are represented as singly linked lists. Each node contains a single digit, and the digits are stored in the same order as the number.

Our task is to add these two numbers and return the resulting number as a linked list.

One important requirement is that the output should not contain leading zeros.

Understanding the Problem

Consider the linked lists:

1 -> 2 -> 3
9 -> 9 -> 9

These represent:

123
999

Their sum is:

The resulting linked list should be:

1 -> 1 -> 2 -> 2

The challenge is that addition starts from the least significant digit, but linked lists store digits from left to right.

Why Direct Traversal Doesn't Work

For normal addition:

  123
+ 999
-----
 1122

We start from the rightmost digits:

3 + 9

However, in a singly linked list, we can only move forward.

This means we cannot directly process digits from right to left.

Key Observation

If we reverse both linked lists, the least significant digits come to the front.

Example:

1 -> 2 -> 3

becomes:

3 -> 2 -> 1

Now addition becomes straightforward because we can process digits from left to right while maintaining carry.

Approach

The solution consists of four major steps:

Remove leading zeros from both lists.
Reverse both linked lists.
Add corresponding digits while handling carry.
Reverse the result to restore the correct order.

Step 1: Remove Leading Zeros

Input lists may contain leading zeros.

Example:

0 -> 0 -> 1 -> 2 -> 3

represents:

Before processing, we skip all leading zeros.

This ensures the output does not contain unnecessary zeros.

Step 2: Reverse Both Lists

Suppose we have:

1 -> 2 -> 3
9 -> 9 -> 9

After reversal:

3 -> 2 -> 1
9 -> 9 -> 9

Now the least significant digits are available first.

Step 3: Perform Addition

Maintain:

carry = 0

For every step:

sum = digit1 + digit2 + carry

New digit:

sum % 10

New carry:

sum / 10

Example:

3 + 9 = 12

Store:

Carry:

Continue until both lists and carry are exhausted.

Step 4: Reverse the Result

The generated list is in reverse order.

Example:

2 -> 2 -> 1 -> 1

Reverse it:

1 -> 1 -> 2 -> 2

This gives the final answer.

Example Walkthrough

Input

head1 = 1 -> 2 -> 3
head2 = 9 -> 9 -> 9

Reverse

3 -> 2 -> 1
9 -> 9 -> 9

Addition

3 + 9 = 12
digit = 2
carry = 1

2 + 9 + 1 = 12
digit = 2
carry = 1

1 + 9 + 1 = 11
digit = 1
carry = 1

0 + 0 + 1 = 1
digit = 1
carry = 0

Result Before Reversal

2 -> 2 -> 1 -> 1

After Reversal

1 -> 1 -> 2 -> 2

Java Solution

class Solution {

    public Node addTwoLists(Node head1, Node head2) {

        head1 = removeLeadingZeros(head1);
        head2 = removeLeadingZeros(head2);

        head1 = reverse(head1);
        head2 = reverse(head2);

        Node dummy = new Node(0);
        Node curr = dummy;

        int carry = 0;

        while (head1 != null || head2 != null || carry != 0) {

            int sum = carry;

            if (head1 != null) {
                sum += head1.data;
                head1 = head1.next;
            }

            if (head2 != null) {
                sum += head2.data;
                head2 = head2.next;
            }

            curr.next = new Node(sum % 10);
            curr = curr.next;

            carry = sum / 10;
        }

        Node result = reverse(dummy.next);

        return removeLeadingZeros(result);
    }

    private Node reverse(Node head) {

        Node prev = null;
        Node curr = head;

        while (curr != null) {
            Node next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }

        return prev;
    }

    private Node removeLeadingZeros(Node head) {

        while (head != null && head.data == 0 && head.next != null) {
            head = head.next;
        }

        return head;
    }
}

Dry Run

Input

63
7

Linked Lists

6 -> 3
7

Reverse

3 -> 6
7

Addition

3 + 7 = 10
digit = 0
carry = 1

6 + 0 + 1 = 7
digit = 7
carry = 0

Result Before Reversal

0 -> 7

After Reversal

7 -> 0

Output

7 -> 0

Complexity Analysis

Time Complexity

O(n + m)

Each list is traversed a constant number of times.

Space Complexity

O(1)

Ignoring the output list, only a few pointers and variables are used.

Key Insight

Since addition naturally proceeds from the least significant digit, reversing the linked lists transforms the problem into the same process used in elementary arithmetic. After reversing, we simply add digits one by one while maintaining carry, build the result, and reverse it back to obtain the final number in the correct order.

Summary

Adding two numbers represented as linked lists becomes challenging because digits are stored from the most significant position to the least significant position. By removing leading zeros, reversing both linked lists, performing digit-by-digit addition with carry handling, and then reversing the result, we can efficiently compute the sum while preserving the required format. This approach runs in O(n + m) time and uses O(1) auxiliary space, making it optimal for large linked lists.