## # Solution

There are many other possible solutions, but none is as good as the following one.

### # Rightmost Not-Nine Digit

Note:

• sentinel node is set to 1 for number is all 9's and o.w. 0
• not-nine digit means all the following digits are 9. So the not-nine digit in 2->9->1->null is 1, and in 0->9->9 is sentinel 0

Complexity:

• time:
• space:
def plusOne(self, head):
sentinel = ListNode(0)
# find the rightmost digit != 9
not_nine = sentinel