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
- Because the digits are most-significant-first, the carry propagates from the tail -- which is the hard direction for a singly linked list.
- 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.
- 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.
- 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.