C++ recursive solution, with O(n) in time


  • 0
    T

    Use recursion, so that we can plus one to the least important digit when visiting it, and deal with the digit before it after returning from the recursive function:

    private:
        int plus(ListNode* head) {
            if(head==NULL) return 0;
            head->val = plus(head->next)+head->val+1;
            if(head->val==10) { 
                head->val=0;
                return 0;
            }
            return -1;
        }
    public:
        ListNode* plusOne(ListNode* head) {
            plus(head);
            if(head->val==0) {
                ListNode* newHead = new ListNode(1);
                newHead->next = head;
                return newHead;
            }
            return head;
        }

Log in to reply
 

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