💬 Discord
Sign In
NeetCode #327LC-2MediumLinked ListNC 150NC 250
← Back to All Problems

#327 · #2 · Add Two Numbers(两数相加)

📌 Problem Statement & Constraints

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

💡 Core Algorithmic Approaches

  1. Walk both lists simultaneously, maintaining a carry.
  2. At each position, sum the two digits (treating a missing node as 0) plus the carry, then emit total % 10 and set carry = total // 10.
  3. Continue while either list has nodes or the carry is non-zero -- the carry condition handles a final carry such as 5 + 5 = 10.
  4. The dummy head removes the need to special-case the first node.

💻 Benchmark Python3 Implementation

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = tail = ListNode(0)
        carry = 0
        while l1 or l2 or carry:
            total = carry
            if l1:
                total += l1.val
                l1 = l1.next
            if l2:
                total += l2.val
                l2 = l2.next
            tail.next = ListNode(total % 10)
            tail = tail.next
            carry = total // 10
        return dummy.next

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(max(m, n)): one pass over the longer list.
💾 Space Complexity
O(max(m, n)) for the result (O(1) extra beyond it).

⚠️ Interview Pitfalls & Follow-ups

  • Forgetting the trailing carry: [5] + [5] must produce [0, 1], so carry belongs in the loop condition.
  • Assuming equal lengths: the lists may differ, so each pointer needs its own bounds check.
  • Converting the lists to integers: it works in Python but defeats the purpose and fails in fixed-width languages.
  • Forgetting the dummy head: the first node would need a special case.