DSA sheet · Linked List · Stack / hash map pattern

Add Two Numbers

This video opens a new pattern in the sheet: linked list with a stack or a hash map. In this pattern we are allowed some extra space (a stack, a map, a list) if the logic needs it, though the extra space is not always part of the best answer. The first problem is the classic school addition, digit by digit with a carry, where each number is stored as a linked list. The teacher goes from "convert to integers" (rejected) → "copy digits into arrays" (works, extra space) → "add while walking both lists" (the optimal one). The "keep going while either list or the carry is left" loop is the heart of it.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Linked list basics you need here (node, walking, dummy node, tail pointer, carry)
• Part A · Brute force: digits into arrays, add with i, j and a carry
• Part B · Optimal: add while walking both lists
• Part C · Revision page

Part 0 · Before starting

What is a linked list node?

A linked list is a chain of nodes. Each node holds a value (val) and a link to the next node (next). The first node is the head. The last node points to None, which means "the end".

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val      # one digit (0-9) in this problem
        self.next = next    # the next node, or None at the end

l1 (head)
 ↓
[2] → [4] → [3] → None

Walking through a list

We use a pointer, for example l1 itself or curr, and move it with l1 = l1.next until it becomes None. A linked list has no index access: there is no l1[2]. To reach position i you walk i steps, which is O(n). That's why our solution walks the lists from the front, once.

Save next before changing a pointer

The next link is the only way to reach the rest of the list. If you overwrite it without keeping the old value, the rest is lost. Here we never rewire the input lists: we only read l1 and l2 and build a fresh answer list, so this danger doesn't come up. It's still the first thing to check whenever you write x.next = ….

The dummy node + tail pointer (for building a new list)

To build a new list one node at a time, we put a fake node in front: dummy = ListNode(0). A second pointer curr always stands on the last node (the tail). To add a node: curr.next = ListNode(d), then curr = curr.next. The dummy stays where it is, so at the end the real head is dummy.next. Without a dummy, the first node would be a special case ("if the answer is empty, this node becomes the head").

[0] → [7] → [0] → [8]
 ↑                 ↑
dummy             curr     → return dummy.next  (the 7)

School addition, carry, % and //

When we add 342 + 465 on paper, we start from the rightmost digit: 2 + 5 = 7. Then 4 + 6 = 10: write 0, carry 1 to the next column. Then 3 + 4 + 1 = 8. Answer 807.

• s % 10 = the last digit of s (the digit we write). 10 % 10 = 0, 7 % 10 = 7.
• s // 10 = what's left after removing the last digit (the carry). 10 // 10 = 1, 7 // 10 = 0.

Part A · Brute force: copy the digits into arrays

LeetCode 2 · Add Two Numbers

1The question in simple words

You get two non-empty linked lists. Each one is a non-negative number, but its digits are stored in reverse order: the head is the ones digit. Add the two numbers and return the sum as a linked list, also in reverse order. There are no leading zeros (except the number 0 itself).

l1:  [2] → [4] → [3] → None      means 342
l2:  [5] → [6] → [4] → None      means 465
                                 342 + 465 = 807
ans: [7] → [0] → [8] → None      (807 written backwards)

Why "reverse order" is a gift. For normal addition we need the last digits first. If the lists were in normal order (2 → 4 → 3 meaning 243), we would have to reverse them, or push the digits on a stack and pop from the end. The teacher shows that idea first (it's the reason this pattern mentions stacks). But here the question has already reversed the numbers for us: the head is the ones digit. So we can just add from the head, left to right, and that is exactly right-to-left on paper.

on paper:            the list holds it as:
    3 4 2                2 → 4 → 3
  + 4 6 5                5 → 6 → 4
  -------                ---------
    8 0 7                7 → 0 → 8     (read the columns right to left
                                        = read the lists left to right)

2What the constraints tell us

• Nodes per list: 1 to 100 → never empty, and small. One linear walk is easily fast enough. (For linked lists we don't write quadratic solutions anyway.)
• Node values 0 to 9, so each node is one digit. This tells us the carry is only ever 0 or 1. The biggest column is 9 + 9 + carry 1 = 19, so the carry can never be 2. If nodes could hold bigger numbers (like 20 + 25 = 45), the carry could be anything 0-9, and we would really need sum // 10 to compute it. Here we could even write "if sum > 9: carry = 1". The teacher still uses % 10 and // 10 because they work for every case.
• 100 digits → this kills the "just convert to an integer" idea (see step 4).
• No leading zeros → we don't need to strip zeros from the input.

3Intuition: do it like on paper

Put one finger on each list. At each step, add the two digits under your fingers plus the carry. Write down the last digit, keep the carry, and move both fingers one step. If one number is shorter, its finger has fallen off the end: treat its digit as 0. When both fingers are off and there's no carry left, you're done.

4Building the logic from examples

Idea 1 (rejected): convert both lists to integers

The first thought: read 342 and 465 as integers, add them to get 807, then break 807 back into digits and build a list. The teacher rejects this because of the constraint: a list can have 100 nodes, so a number can have 100 digits. An int holds about 10 digits and a long about 19, so the number won't fit. If the lists were at most 15-18 digits, it could have worked.

class Solution:
    def addTwoNumbers(self, l1, l2):
        def to_int(node):
            num, place = 0, 1
            while node:
                num += node.val * place    # head is the ones digit
                place *= 10
                node = node.next
            return num

        total = to_int(l1) + to_int(l2)
        dummy = ListNode(0)
        curr = dummy
        while True:
            curr.next = ListNode(total % 10)
            curr = curr.next
            total //= 10
            if total == 0:
                break
        return dummy.next

Idea 2 (the brute force): copy the digits into two arrays

Read l1 into an array a = [2, 4, 3] and l2 into b = [5, 6, 4]. Now index i walks a, index j walks b, and we keep a carry starting at 0.

• i = 0, j = 0: 2 + 5 + 0 = 7. Not more than 9 → write 7, carry stays 0.
• i = 1, j = 1: 4 + 6 + 0 = 10. More than 9 → we can't write "10" in one node. Write 10 % 10 = 0, carry 10 // 10 = 1.
• i = 2, j = 2: 3 + 4 + 1 = 8 → write 8, carry 0.

Answer array: [7, 0, 8]. Then build a linked list from it with a dummy node.

How long can the answer be? max(n, m) + 1

The two lists don't have to be the same length. The teacher changes the example: l1 = 2 → 4 → 3, l2 = 5 → 6 → 4 → 5 → 6 (lengths 3 and 5). And she shows that a final carry can add one extra digit: e.g. if the last column is 5 + 4 + 1 = 10, we write 0 and still have carry 1, which becomes a new last digit 1. So the answer has at most max(n, m) + 1 digits.

The loop condition: i < n or j < m or carry

When should we stop? Not when i runs out, and not even when both run out:

• If a has ended but b still has digits → keep going (treat the missing digit as 0).
• If both have ended but carry is 1 → keep going one more time, to write that carry as the last digit.

So we keep looping while any of the three is still there, and that is why it's or, not and.

5Approach steps

1. Copy l1's digits into a and l2's digits into b.
2. Set i = j = carry = 0, and an empty answer array.
3. While i < len(a) or j < len(b) or carry: s = carry + (a[i] if it exists) + (b[j] if it exists). Append s % 10, set carry = s // 10, and move i and j.
4. Build a linked list from the answer array with a dummy node, and return dummy.next.

6Code (Python)

class Solution:
    def addTwoNumbers(self, l1, l2):
        a, b = [], []
        while l1:                        # copy digits of l1
            a.append(l1.val)
            l1 = l1.next
        while l2:                        # copy digits of l2
            b.append(l2.val)
            l2 = l2.next

        ans = []
        i = j = carry = 0
        while i < len(a) or j < len(b) or carry != 0:
            s = carry
            if i < len(a):
                s += a[i]
                i += 1
            if j < len(b):
                s += b[j]
                j += 1
            ans.append(s % 10)           # the digit to write
            carry = s // 10              # 0 or 1

        dummy = ListNode(0)              # build the answer list
        curr = dummy
        for d in ans:
            curr.next = ListNode(d)
            curr = curr.next
        return dummy.next

7Code line by line

8Dry run: different lengths with a final carry

l1 = 9 → 9 (means 99), l2 = 1 (means 1). 99 + 1 = 100, so the answer should be 0 → 0 → 1. a = [9, 9], b = [1].

Step 3 only runs because of the or carry part of the condition. Without it, we would lose the leading 1 and return 0 → 0 (which means 0, wrong).

9Complexity & remember

• Time O(n + m): one walk over each list to copy, then the loop runs max(n, m) (+1) times, then building the answer. All linear. The teacher sums it up as O(max(n, m)), up to a constant.
• Space O(n + m) for the two arrays, plus the answer array and answer list of max(n, m) + 1 digits.

Part B · Optimal: add while walking both lists

1The question (same as Part A)

Same input and output. The new rule: don't copy the digits into arrays first. Work directly on the nodes.

2What the constraints tell us

Same as Part A: at least 1 node each, so no empty-list base case is needed. Digits 0-9, so the carry is 0 or 1. Up to 100 nodes, so no integer conversion.

3Intuition: we were already walking both lists

The teacher's key observation: in the brute force, we already walked l1 and l2 just to copy the digits. Both walks started at the head, at the same time. So why not add the digits during that walk, instead of saving them first? While walking, we add the two current digits + carry, and attach a new node to a growing answer list.

4Building the logic

Step 1: the answer list starts with a dummy

dummy = ListNode(0), curr = dummy. Each new digit is attached at curr.next, then curr moves forward.

Step 2: don't write l1.val + l2.val directly

Adding l1.val + l2.val only works while both lists still have nodes. When one ends, it's None, and None.val crashes. Handling that separately would need extra loops ("while only l1 is left, keep adding carry + l1.val …", and the same for l2). The teacher avoids all of that:

• Start s = carry.
• If l1 is not None: add l1.val and move l1 = l1.next.
• If l2 is not None: add l2.val and move l2 = l2.next.

A list that has ended just adds nothing (like a 0 digit).

Step 3: write the digit, keep the carry

carry = s // 10, then curr.next = ListNode(s % 10), then curr = curr.next. As in Part A, these two operations work for both small and large sums, so no if/else is needed.

Step 4: the same loop condition

while l1 or l2 or carry: keep going while either list has nodes left, or a carry is still waiting to be written.

Step 5: return dummy.next

When the loop ends, curr is on the last digit, and the dummy is in front of the first one. The real head (the 7 in our example) is dummy.next.

5Approach steps

1. dummy = ListNode(0), curr = dummy, carry = 0.
2. While l1 or l2 or carry: s = carry; add and advance l1 if present; add and advance l2 if present.
3. carry = s // 10; attach ListNode(s % 10); move curr.
4. Return dummy.next.

6Code (Python)

class Solution:
    def addTwoNumbers(self, l1, l2):
        dummy = ListNode(0)              # fake head of the answer
        curr = dummy                     # tail of the answer
        carry = 0

        while l1 is not None or l2 is not None or carry != 0:
            s = carry
            if l1 is not None:
                s += l1.val
                l1 = l1.next
            if l2 is not None:           # separate if: both may add
                s += l2.val
                l2 = l2.next
            carry = s // 10
            curr.next = ListNode(s % 10)
            curr = curr.next

        return dummy.next

7Code line by line

8Dry run

Example 1: l1 = 2 → 4 → 3, l2 = 5 → 6 → 4

Snapshot after step 2:

l1:  [2] → [4] → [3] → None          l2:  [5] → [6] → [4] → None
                  ↑                                      ↑
                  l1                                     l2
ans: [0] → [7] → [0]          carry = 1
      ↑           ↑
    dummy        curr

Example 2: different lengths + extra carry (the teacher's variant)

l1 = 2 → 4 → 3 (342), l2 = 5 → 6 → 4 → 5 → 6 (65465). Sum = 65807.

l1 ran out after step 3, but the loop kept going because l2 was still alive. The answer has max(3, 5) = 5 digits. With l1 = 9 → 9 and l2 = 1, a 3rd step runs only for the carry and adds a new node 1, giving max(2, 1) + 1 = 3 digits.

(While explaining, the teacher misspeaks once and calls 2 + 5 "nine", and later says "greater than 12, modulo gives 2". The ideas are right: 2 + 5 = 7, and a sum of 12 gives digit 2 and carry 1.)

9Complexity & remember

• Time O(max(n, m)): the loop runs once per column. With lengths 2 and 10, it runs 10 times, or 11 if a final carry is left.
• Space O(max(n, m)): only for the answer list (max(n, m) + 1 nodes at most). We no longer copy the inputs into arrays, so the only extra variables are dummy, curr, carry and s.

Part C · Revision page

def build(vals):
    dummy = ListNode(0)
    t = dummy
    for v in vals:
        t.next = ListNode(v)
        t = t.next
    return dummy.next

def to_list(head):
    out = []
    while head:
        out.append(head.val)
        head = head.next
    return out

s = Solution()
print(to_list(s.addTwoNumbers(build([2, 4, 3]), build([5, 6, 4]))))   # [7, 0, 8]
print(to_list(s.addTwoNumbers(build([0]), build([0]))))               # [0]
print(to_list(s.addTwoNumbers(build([9, 9]), build([1]))))            # [0, 0, 1]

Based on this video: Add Two Numbers