⚡Flashcard Drill➔
NeetCode #328LC-445MediumLinked List
← Back to All Problems

#328 · #445 · Add Two Numbers II(两数相加 II)

📌 Problem Statement & Constraints

You are given two non-empty linked lists representing two non-negative integers in most significant first order. Add the two numbers and return the sum as a linked list in the same order. You may not reverse the input lists. Constraints: the number of nodes in each list is in [1, 100], 0 <= Node.val <= 9.

💡 Core Algorithmic Approaches

  1. Because the digits are most-significant-first, the carry propagates from the tail -- which is the hard direction for a singly linked list.
  2. Two clean options: reverse both lists, add as in Add Two Numbers, then reverse the result; or push both lists onto stacks and pop digits.
  3. The problem says you may not reverse the input lists; the first option reverses them destructively, which some interpretations forbid. The stack version avoids that entirely.
  4. Either way the algorithm is O(m + n) time.

💻 Benchmark Python3 Implementation

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # stack-based: avoids mutating the inputs
        s1, s2 = [], []
        cur = l1
        while cur:
            s1.append(cur.val)
            cur = cur.next
        cur = l2
        while cur:
            s2.append(cur.val)
            cur = cur.next
        carry = 0
        head = None
        while s1 or s2 or carry:
            total = carry
            if s1:
                total += s1.pop()
            if s2:
                total += s2.pop()
            # build the result from the least significant digit, prepending
            node = ListNode(total % 10)
            node.next = head
            head = node
            carry = total // 10
        return head

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(m + n): each digit is pushed and popped once.
💾 Space Complexity
O(m + n) for the two stacks (the reverse-and-add variant uses O(1) extra beyond the output but mutates the inputs).

⚠️ Interview Pitfalls & Follow-ups

  • Building the result in the wrong direction: since the digits are processed least-significant-first, each new node must be prepended to the result.
  • Mutating the input lists: the reverse-and-add approach reverses the inputs in place, which the problem forbids.
  • Forgetting the final carry: [5] + [5] must produce [1, 0].
  • Assuming equal lengths: the lists may differ, so each stack needs its own emptiness check.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems