LC: 369. Plus One Linked List - spiralgo/algorithms GitHub Wiki

369. Plus One Linked List

The Essence:

Simply incrementing the final node in the list is not enough. What if that value was 9? Checking this and incrementing the previous value is not enough too. The last value that is not 9 should be incremented, for example in a sequence like 125999 -> 126000.

One needs to recognize how the local changes can affect the global result.

In a sequence of just 9's (999), a new node will be needed at the start of the list.

Details:

The new node can be created as a sentinel node. The last non-nine none is initially this, but it can get updated. All 9's at the end are set to 0, while the last non-nine is incremented. The sentinel is return if it has also been incremented, otherwise returning the head is the right choice.