There are many other possible solutions, but none is as good as the following one.
# Rightmost Not-Nine Digit
sentinelnode is set to
1for number is all
9's and o.w.
not-ninedigit means all the following digits are 9. So the not-nine digit in
1, and in
def plusOne(self, head): sentinel = ListNode(0) sentinel.next = head # find the rightmost digit != 9 not_nine = sentinel while head: if head.val!=9: not_nine = head head = head.next # increase this rightmost not-nine digit by 1 not_nine.val += 1 not_nine = not_nine.next # set all the following nines to zeros while not_nine: not_nine.val = 0 not_nine = not_nine.next return sentinel if sentinel.val else sentinel.next