Back to Beginner: I/O, Arithmetic, Loops
Q12Question 12 of 30

Add Two Numbers Represented by Linked Lists

Key Concepts
  • Digits stored in reverse order means the head is the ones place, which is perfect because addition starts from the ones place.
  • Walk both lists together, add corresponding digits plus a running carry, store sum % 10 as the new digit, and propagate sum / 10 as the carry.
  • The loop continues while either list has nodes left OR the carry is non-zero, handling the final carry-out.
  • A dummy head node simplifies result-list construction; return dummy.next as the answer.
  • Handle lists of different lengths by treating a missing node as digit zero.
  • Never convert the lists to a long and add, because that overflows for large numbers and defeats the purpose of the digit-list representation.

Definition

Walk both lists adding digit plus digit plus carry, write the ones digit, carry the rest: grade-school addition as a linked-list pass.
  • Reverse-order digits – the head of each list is the ones place, so addition naturally starts from the head.
  • Column addition – for each pair of nodes, compute digit1 + digit2 + carry; the new digit is sum % 10 and the new carry is sum / 10.
  • Loop condition – while (a != null || b != null || carry != 0) covers different-length lists and the final carry-out.
  • Dummy head – a sentinel node simplifies appending; return dummy.next as the result.
  • Complexity – O(max(n, m)) time and space, where n and m are the list lengths.

National Bank of India adds two huge end-of-day amounts digit by digit. The digits are written on cards laid out from the smallest place value first. A clerk adds the two ones cards, writes the ones result and carries the tens over, then adds the tens cards plus the carry, exactly like adding on paper starting from the rightmost digit.

Understanding the Concepts

What is the problem?

Two non-empty linked lists represent two non-negative integers. Each node holds a single digit (0-9) and digits are stored in reverse order: the head is the ones place. Add the two numbers and return the sum as a linked list, also in reverse order.

Example: 342 + 465 = 807. As lists: 2 -> 4 -> 3 plus 5 -> 6 -> 4 equals 7 -> 0 -> 8.

How do you implement it in Java?

JAVA
package com.bank.service;

public class DigitListAdder {

    static class ListNode {
        int val;
        ListNode next;
        ListNode(int val) { this.val = val; }
    }

    public static ListNode addTwoNumbers(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        int carry = 0;

        while (a != null || b != null || carry != 0) {
            int x = (a != null) ? a.val : 0;
            int y = (b != null) ? b.val : 0;
            int sum = x + y + carry;

            tail.next = new ListNode(sum % 10);
            tail = tail.next;
            carry = sum / 10;

            if (a != null) a = a.next;
            if (b != null) b = b.next;
        }
        return dummy.next;
    }

    public static void main(String[] args) {
        // 342 + 465 = 807 (amounts in hundreds at National Bank of India)
        ListNode a = new ListNode(2);
        a.next = new ListNode(4);
        a.next.next = new ListNode(3);

        ListNode b = new ListNode(5);
        b.next = new ListNode(6);
        b.next.next = new ListNode(4);

        ListNode result = addTwoNumbers(a, b);
        StringBuilder sb = new StringBuilder();
        while (result != null) {
            sb.append(result.val).append(" -> ");
            result = result.next;
        }
        System.out.println(sb.toString().replaceAll(" -> $", ""));
    }
}
TEXT
7 -> 0 -> 8

Why include carry in the loop condition?

The carry handles the case where both lists are exhausted but the last column produced a carry-out. For example, 5 + 5 = 10. Both lists have one node each, but after processing them the carry is 1, so the loop must run one more time to produce the leading 1.

JAVA
// a = [5], b = [5]
// Step 1: 5 + 5 + 0 = 10 → digit 0, carry 1
// Step 2: both null, carry = 1 → digit 1, carry 0
// Result: 0 -> 1 (which is 10 in reverse)

How do you handle lists of different lengths?

The ternary expressions (a != null) ? a.val : 0 treat a missing node as digit zero. This avoids special-case branches and handles any length difference naturally.

Why not convert to a number and add?

Converting to a long and adding defeats the purpose. The digit-list representation exists precisely because the numbers can be too large for any fixed-size type. A number with 100 digits would overflow every primitive.

What are edge cases?

JAVA
// Both single digit, no carry: [3] + [4] = [7]
// Both single digit, with carry: [9] + [1] = [0, 1]
// Very different lengths: [9,9,9] + [1] = [0,0,0,1]
// One list much longer: [1] + [9,9,9,9] = [0,0,0,0,1]

What are common mistakes?

JAVA
// Wrong: loop stops when BOTH are null, forgetting carry
while (a != null || b != null) { ... }
// Misses the final carry! [5] + [5] would give [0] instead of [0, 1]

// Correct: include carry in condition
while (a != null || b != null || carry != 0) { ... }

What about the forward-order variant?

If digits are stored in forward order (head is the most significant digit), you need to either reverse both lists first and then add, or use a stack-based approach to process from the tail. The reverse approach is simpler.

What should a senior engineer know?

This digit-by-digit approach is essentially arbitrary-precision addition, the same idea that BigInteger and BigDecimal implement internally. In a real banking system at National Bank of India, legacy mainframe feeds transmit very large amounts as digit streams, and this algorithm adds them correctly regardless of size.

The dummy head pattern is reusable across many linked-list construction problems. It avoids null checks on the first node and keeps the code clean.

What are common interview follow-up questions?

  • How would you handle digits stored in forward order instead of reverse?
  • Can you add three such numbers in one pass?
  • What is the maximum length of the result list?

Visual Overview

DIAGRAM
  a:  2 → 4 → 3     (342)
  b:  5 → 6 → 4     (465)

  Step 1: 2+5+0=7  → digit 7, carry 0
  Step 2: 4+6+0=10 → digit 0, carry 1
  Step 3: 3+4+1=8  → digit 8, carry 0

  Result: 7 → 0 → 8  (807)

Key Takeaway

Adding two numbers stored as digit linked lists in reverse order is grade-school column addition expressed as a single forward pass. Because the heads of both lists are the ones place, you add the two current digits plus a running carry, write the ones digit into a new result node, and propagate the tens digit as the carry. The loop continues while either list has digits remaining or the carry is still non-zero, which correctly produces a new leading digit when the sum grows an extra place.

The algorithm runs in time proportional to the longer of the two lists. Different lengths are handled by treating any missing node as a zero digit, which the ternary expressions do without special branches.

The dummy head node keeps result-list construction clean: you always append to tail.next and return dummy.next so the throwaway anchor is never part of the answer. The whole approach is really arbitrary-precision addition, the same idea that BigInteger and BigDecimal implement internally.

In a banking project at National Bank of India, legacy mainframe feeds transmitted very large end-of-day amounts as digit streams in exactly this reverse order. The numbers could be too large for a fixed-size long, so converting to a primitive was not an option. This digit-by-digit addition kept the total exact regardless of size.

Remember one sentence: add digit by digit with a carry, and include the carry in the loop condition so the final carry-out produces its own node.

---

Share
Use ← → arrow keys to navigate