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
- The carry propagates from the tail, so reversing the list makes the addition a simple left-to-right walk.
- Reverse, add one with a carry loop, then reverse back.
- 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.
- 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.