Plus One Linked List

Linked List
https://leetcode.com/problems/plus-one-linked-list

# Solution

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

Let nn be the length of linked list.

# Rightmost Not-Nine Digit

Note:

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

Complexity

time: O(n)O(n)
space: O(1)O(1)

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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20