C++ O(n) recursive solution


  • 0
    Q

    First find the tail, update tail's val and return carry out. Recursively update the parent val and return carry out until the top, where head's parent is NULL. If top carry out is 1, create a new head, whose child is the old head.

    ListNode* plusOne(ListNode* head) {
        ListNode* newHead;
        int carry = recur(head, NULL);
        if (carry == 0)
            return head;
        newHead = new ListNode(1);
        newHead->next = head;
        return newHead;
    }
    
    int recur(ListNode* cur, ListNode* parent) {
        if (cur==NULL) {
            int tmp = parent->val + 1;
            parent->val = tmp % 10;
            int carry = tmp / 10;
            return carry;
        }
        int carry = recur(cur->next, cur);
        if (parent==NULL) return carry;
        
        int tmp = parent->val + carry;
        parent->val = tmp % 10;
        carry = tmp / 10;
        return carry;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.