369. Plus One Linked List - cocoder39/coco39_LC GitHub Wiki

369. Plus One Linked List

dummy node + two pointers.

the trick is finding out consecutive '9's at the end of the list. Thus p2 points to the last node that is not belong to the consecutive '9's.

tip:

• use dummy node to handle input like '9', '999'...
• ListNode dummy = ListNode(0) would report bug since dummy is a local temporary variable, which would expire when the program ends. Thus use ListNode* dummy = new ListNode(0) to allocate memory for dummy.

ListNode* plusOne(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* fast = dummy;
        ListNode* slow = dummy;
        while (fast->next) {
            fast = fast->next;
            if (fast->val != 9) {
                slow = fast; //the start point after which is 9s to the end
            }
        }
        
        while (slow) {
            if (slow->val != 9) {
                slow->val = slow->val + 1;
            }
            else {
                slow->val = 0;
            }
            slow = slow->next;
        }
        return dummy->val ? dummy : dummy->next;
    }