Adding Two Meter Readings

TIP103 Unit 11 Session 1 (Click for link to problem statements)

Adding Two Meter Readings

Two utility meters store their readings as linked lists of single digits in reverse order (ones digit first). Given the heads l1 and l2, add the two numbers and return the sum as a linked list in the same reversed format.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def add_two_numbers(l1, l2):
    pass

Problem Highlights

• 💡 Difficulty: Medium
• ⏰ Time to complete: 20-30 mins
• 🛠️ Topics: Linked Lists, Math, Carry Propagation

1: U-nderstand

Understand what the interviewer is asking for by using test cases and questions about the problem.

• Established a set (2-3) of test cases to verify their own solution later.
• Established a set (1-2) of edge cases to verify their solution handles complexities.
• Have fully understood the problem and have no clarifying questions.
• Have you verified any Time/Space Constraints for this problem?

• Q: How is each meter reading stored?

  • A: As a linked list of single digits in reverse order, so the ones digit comes first. The reading 342 is stored as 2 -> 4 -> 3.

• Q: What should the function return?

  • A: The head of a new linked list holding the sum's digits in the same reversed format.

• Q: Can the two readings have different numbers of digits?

  • A: Yes. Once the shorter list runs out, treat its missing digits as 0 and keep adding.

HAPPY CASE
Input: l1 = 2 -> 4 -> 3 (represents 342), l2 = 5 -> 6 -> 4 (represents 465)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807, stored in reverse as 7 -> 0 -> 8.

Input: l1 = 5 -> 4 (represents 45), l2 = 8 (represents 8)
Output: 3 -> 5
Explanation: 45 + 8 = 53, stored in reverse as 3 -> 5. The lists have different lengths.

EDGE CASE
Input: l1 = 9 -> 9 -> 9 (represents 999), l2 = 1 (represents 1)
Output: 0 -> 0 -> 0 -> 1
Explanation: 999 + 1 = 1000. The carry ripples through every digit, and the result is longer than either input list.

2: M-atch

Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.

For Linked List Problems, we can consider the following approaches:

• Simultaneous Traversal: Walk both lists in lockstep, processing one digit from each list per step.
• Dummy Head Node: Build the result list behind a placeholder node so we never special-case the first digit.
• Elementary Addition with Carry: The reversed storage lines the digits up exactly like grade-school column addition — add the ones digits first and carry into the next place value.

3: P-lan

Plan the solution with appropriate visualizations and pseudocode.

General Idea:
Because the digits are stored ones-first, we can add the numbers the same way we add on paper: sum the current pair of digits plus any carry, write down the ones digit of that sum as a new node, and pass the tens digit forward as the carry. Continue until both lists are exhausted and no carry remains.

1) Create a dummy head node and a `current` pointer starting at the dummy. Set `carry = 0`.
2) While `l1` is not None, or `l2` is not None, or `carry` is nonzero:
   a) Let `digit1` be `l1.val` if `l1` exists, else 0. Same for `digit2` and `l2`.
   b) Compute `total = digit1 + digit2 + carry`.
   c) Set `carry = total // 10` and append a new node holding `total % 10` after `current`.
   d) Advance `current`, and advance `l1` and `l2` if they exist.
3) Return `dummy.next`, the head of the sum list.

⚠️ Common Mistakes

• Dropping the final carry, e.g. returning 9 -> 9 + 1 as 0 -> 0 instead of 0 -> 0 -> 1.
• Stopping the loop when the shorter list ends instead of continuing through the longer list.
• Trying to convert the lists to integers first — that works in Python but sidesteps the linked list pattern the interviewer is testing.
• Forgetting to advance l1/l2 only when they are not None, causing an AttributeError on lists of different lengths.

4: I-mplement

Implement the code to solve the algorithm.

def add_two_numbers(l1, l2):
    dummy = ListNode()   # Placeholder head so the first digit needs no special case
    current = dummy
    carry = 0

    # Keep going while either list has digits or a carry remains
    while l1 or l2 or carry:
        digit1 = l1.val if l1 else 0
        digit2 = l2.val if l2 else 0

        total = digit1 + digit2 + carry
        carry = total // 10               # Carry into the next place value
        current.next = ListNode(total % 10)
        current = current.next

        # Advance each list only if it still has nodes
        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    return dummy.next

5: R-eview

Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.

• Input: l1 = 2 -> 4 -> 3, l2 = 5 -> 6 -> 4 (342 + 465)

  • Step 1: 2 + 5 + 0 = 7, carry 0, append 7.
  • Step 2: 4 + 6 + 0 = 10, carry 1, append 0.
  • Step 3: 3 + 4 + 1 = 8, carry 0, append 8.
  • Both lists and the carry are exhausted, so the loop stops.
  • Output: 7 -> 0 -> 8, which prints as 7 0 8 and represents 807.

• Input: l1 = 9 -> 9 -> 9, l2 = 1 (999 + 1)

  • Step 1: 9 + 1 + 0 = 10, carry 1, append 0. l2 is now exhausted.
  • Step 2: 9 + 0 + 1 = 10, carry 1, append 0.
  • Step 3: 9 + 0 + 1 = 10, carry 1, append 0.
  • Step 4: both lists are done but carry is 1, so append 1.
  • Output: 0 -> 0 -> 0 -> 1, representing 1000.

6: E-valuate

Evaluate the performance of your algorithm and state any strong/weak or future potential work.

Assume M is the number of digits in l1 and N is the number of digits in l2.

• Time Complexity: O(max(M, N)) because the loop runs once per digit of the longer list, plus at most one extra iteration for a final carry.
• Space Complexity: O(max(M, N)) for the result list, which holds max(M, N) digits (or one more when the sum carries into a new place value). Ignoring the output, only O(1) extra space is used.