Cracking The Coding Interview Together – Problem 2.5: Sum Lists

Welcome back.

If you’ve been following the series, you already know the drill. We don’t rush to code. We don’t jump straight to “the clever solution.” We slow down, understand the problem, ask questions, and think the way an interviewer expects us to think.

Today’s problem looks simple on the surface. Two linked lists. Digits. Addition. But like many interview questions, the trick isn’t the math — it’s how cleanly you reason about the structure.

As always, we’ll follow the same structure that you would use in a real interview.

1. Understand the problem statement together
2. Ask any questions, that you would like to ask the interviewer
3. I would urge you to take your time here and try to come up with your own solution before going forward
4. Think how you would go about solving the problem(you would be talking out loud in front of the actual interviewer)
5. Write code and understand how it works and explain it to your interviewer

Problem statement

Sum Lists: You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list.

Analyse the problem statement together

Before thinking about code, let’s slow down and really understand what’s being asked.

Input

If the number 617 is represented as a linked list, it would look like this:

7 -> 1 -> 6

Why? Because the digits are stored in reverse order.

Similarly, 295 would be:

5 -> 9 -> 2

Now if we add these two numbers:

617 + 295 = 912

Output

2 -> 1 -> 9

That’s it. That’s the core problem.

Before you go any further, stop here for a moment.

Ask yourself:

• What makes this different from adding two numbers normally?
• What constraints does a linked list introduce?
• What information do we not have access to?

If you’re already forming ideas in your head — good. That’s exactly what should happen.

Questions for the interviewer

Now we do what many candidates skip — we clarify assumptions.

This step is not optional. Interviewers care deeply about how you handle ambiguity.

Here are the questions I would ask:

1. Can the two linked lists be of different lengths?
   (e.g., one number has more digits than the other)
2. Can either list be null?
   If so, what should we return?
3. Are the digits always between 0 and 9?
   Or can nodes contain invalid values?
4. Should we handle carry-over the same way we do in normal addition?
   (This sounds obvious, but it’s still worth confirming.)
5. Do we need to modify the input lists, or return a new one?

Let’s assume the interviewer answers:

• Yes, lists can be of different lengths
• A null list represents the number 0
• Each node always contains a digit from 0 to 9
• Yes, carry-over must be handled
• Return a new linked list (do not modify inputs)

Perfect. Now we can move forward with confidence.

Think about the Solution

Before reading further, I really want you to pause here.

Try to explain the solution out loud — even if you’re alone.

Ask yourself:

• How would I add two numbers digit by digit?
• How do I keep track of carry?
• What happens when one list ends before the other?

If you can explain this in words, the code will be easy.

If you can’t explain it yet — that’s fine. Let’s walk through it together.

Let’s start with how normal addition works.

When you add two numbers:

• You start from the least significant digit
• You add digits plus any carry
• You store the result digit
• You carry over if the sum is ≥ 10

Now notice something important.

Because the digits are stored in reverse order, the linked list already starts at the least significant digit.

That’s a gift.

We don’t need to reverse anything. We don’t need stacks. We don’t need recursion (yet).

We can simply:

• Traverse both lists at the same time
• Add corresponding digits
• Track carry
• Build the result list as we go

This is one of those problems where the data structure actually makes things easier — if you notice it.

High-Level Algorithm

Here’s the plan:

1. Create a dummy head for the result list
2. Initialize a carry variable to 0
3. Loop while either list still has nodes, or there is a carry left
4. For each step:
   • Read digit from list1 (or 0 if null)
   • Read digit from list2 (or 0 if null)
   • Add digits + carry
   • Create a new node with (sum % 10)
   • Update carry to (sum / 10)
5. Return the list starting after the dummy head

That’s it.

No tricks. No clever hacks. Just disciplined thinking.

Write code and explain

Now let’s translate this idea into code.

Java code

Node Definition (Assumed)

class ListNode {
    int val;
    ListNode next;

    ListNode(int val) {
        this.val = data;
        this.next = null;
    }
}

SumLists Function

public class SumLists {

    public static ListNode addLists(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;

        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int value1 = (l1 != null) ? l1.val : 0;
            int value2 = (l2 != null) ? l2.val : 0;

            int sum = value1 + value2 + carry;
            carry = sum / 10;

            current.next = new ListNode(sum % 10);
            current = current.next;

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

        return dummyHead.next;
    }
}

Time & Space Complexity

Time Complexity

• If the two lists have lengths n and m, we traverse both once i.e. O(max(n, m))

Space Complexity

• We create a new linked list for the result i.e. O(max(n, m))

Explain the Code Like You Would in an Interview

Why Use a Dummy Head?

Using a dummy head simplifies list construction.

Instead of handling the “first node” as a special case, we always attach new nodes to current.next. At the end, we simply return dummyHead.next.

This avoids bugs and keeps the code clean.

Why the while Condition Looks the Way It Does

while (l1 != null || l2 != null || carry != 0)

This is crucial.

• We continue while there are digits left in either list
• We also continue if there’s a carry left after both lists end

This handles cases like:

9 -> 9 -> 9
+
1

Which should produce:

0 -> 0 -> 0 -> 1

Without the carry != 0 condition, we’d lose that final digit.

Handling Different Length Lists

Notice this part:

int value1 = (l1 != null) ? l1.val : 0;
int value2 = (l2 != null) ? l2.val : 0;

If one list ends earlier, we treat its value as 0.

That’s exactly how you’d do it by hand.

Carry Logic

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

This mirrors elementary-school addition.

We store the last digit and carry the rest forward.

Common Mistakes to Avoid

Let’s talk about what often goes wrong:

• Forgetting to handle carry at the end
• Stopping the loop too early
• Modifying the input lists accidentally
• Overcomplicating the solution with stacks or recursion

If you find yourself reaching for complex tools here — pause. The problem doesn’t need them.

Final Thoughts

This is one of those problems that quietly tests a lot:

• Can you reason with linked lists?
• Can you model real-world logic in code?
• Can you explain your thinking clearly?

The math is simple. The thinking is what matters.

If you can walk an interviewer through this solution calmly, step by step, you’re doing it right.

As always, I encourage you to:

• Try coding this yourself
• Modify the inputs
• Break it intentionally and fix it again

That’s how these patterns stick.

I’ll see you in the next one.

Until then — happy coding.