369. Plus One Linked List

Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

Example :

Input: [1,2,3]
Output: [1,2,4]

ListNode* plusOne(ListNode* head) { // time: O(n); space: O(1)
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* i = dummy, *j = dummy; // i: the most significant digit to increment
    while (j->next) {
        j = j->next;
        if (j->val != 9) i = j; // i~j are all digit '9'
    }
    if (j->val != 9) j->val++;
    else {
        i->val++;
        i = i->next;
        while (i) {
            i->val = 0;
            i = i->next;
        }
    }
    ListNode* res = nullptr;
    if (dummy->val == 0) {
        res = dummy->next;
        delete dummy;
    } else {
        res = dummy;
    }
    return res;
}