⚡Flashcard Drill➔
NeetCode #313LC-369MediumLinked ListNC Algo100
← Back to All Problems

#313 · #369 · Plus One Linked List(给单链表加一)

📌 Problem Statement & Constraints

Given a non-negative integer represented as a linked list of digits in most significant first order, add one to it and return the result in the same format. Constraints: the number of nodes is in [1, 100], 0 <= Node.val <= 9, no leading zeros except the number 0 itself.

💡 Core Algorithmic Approaches

  1. The carry propagates from the tail, so reversing the list makes the addition a simple left-to-right walk.
  2. Reverse, add one with a carry loop, then reverse back.
  3. An alternative avoids the reversals: find the rightmost digit that is not 9, increment it, and set all following digits to 0. If every digit is 9, prepend a 1 and zero the rest.
  4. The reversal approach is easier to reason about; the non-reversal approach is a nice follow-up.

💻 Benchmark Python3 Implementation

class Solution:
    def plusOne(self, head: Optional[ListNode]) -> Optional[ListNode]:
        def reverse(node):
            prev = None
            while node:
                node.next, prev, node = prev, node, node.next
            return prev

        head = reverse(head)
        cur = head
        carry = 1                          # the +1 to add
        prev = None
        while cur and carry:
            s = cur.val + carry
            cur.val = s % 10
            carry = s // 10
            prev = cur
            cur = cur.next
        if carry:                          # all digits were 9
            prev.next = ListNode(1)
        return reverse(head)


# Variant without reversal: find the rightmost digit that is not 9
class Solution2:
    def plusOne(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0, head)
        last_not_nine = dummy          # dummy acts as the "leading 1" slot
        cur = head
        while cur:
            if cur.val != 9:
                last_not_nine = cur
            cur = cur.next
        last_not_nine.val += 1         # increment the rightmost non-9
        cur = last_not_nine.next
        while cur:
            cur.val = 0                # everything after becomes 0
            cur = cur.next
        return dummy.next if last_not_nine is not dummy else dummy

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one or two passes.
💾 Space Complexity
O(1): the reversal version relinks in place; the second version only writes digits.

⚠️ Interview Pitfalls & Follow-ups

  • Adding one to the head: the digits are most-significant-first, so the carry starts at the tail.
  • Forgetting the all-nines case: [9, 9] must become [1, 0, 0], requiring a new leading node.
  • Reversing and forgetting to reverse back: the result would be in the wrong order.
  • Mutating the input list in place in the first variant: reversing twice restores the original node order, but the node objects are the same as the input -- acceptable here since the problem expects a new value arrangement.
⚡
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