Problem statement

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

Solution

Add sentinel variable with $0$ to the start of our linked list. Now, we need to find how many $9$ we have in the end, for example $4192995289999$ has four $9$ in the end. How can we find it? Traverse the list with two pointers and find the place for the last group of $9$ — if next digit is not $9$, we put two pointers to this element, else, we move only fast element. In the end we have slow pointer just before the last group of $9$. Add $1$ to value of slow pointer and change all next elements to $0$. Return dummy variable if it is equal to $1$ and next one if it is equal to $0$.

Complexity

Time complexity is $O(n)$, more precisely $2n$ — we have full pass for slow and fast pointers, time complexity is $O(1)$.

Code

class Solution:
    def plusOne(self, head):
        dummy = ListNode(0)
        dummy.next = head
        
        slow, fast = dummy, dummy
        while fast.next:
            if fast.next.val != 9:
                slow, fast = fast.next, fast.next
            else:
                fast = fast.next
                
        slow.val += 1
        while slow.next:
            slow.next.val = 0
            slow = slow.next
        
        return dummy.next if dummy.val == 0 else dummy

Remark

See Problem 0066. Plus One, which is exactly the same, but we have array, not list there.