4ms simple and iterative solution in C++


  • 0
    D

    The algorithm is straightforward: reverse, add, then reverse. I could combine the add and later reversion steps into 1 for saving 1 traversing, but it would make the code uglier.

    ListNode* plusOne(ListNode* head) {
        if (head == NULL)
            return NULL;
            
        Reverse(&head);
        AddOne(head);
        Reverse(&head);
    
        return head;
    } // O(n) time, O(1) space
    
    void AddOne(ListNode *head) {
        int r = 1;
        ListNode *cur = head, *prev = NULL;
        while (cur) {
            int tmp = r + cur->val;
            cur->val = tmp % 10;
            r = tmp / 10;
            prev = cur;
            cur = cur->next;
        }
        if (r)
            prev->next = new ListNode(1);
    }
    
    void Reverse(ListNode **head) {
        ListNode *prev = NULL, *cur = *head;
        while (cur) {
            ListNode *next = cur->next;
            cur->next = prev;
            prev = cur;
            cur = next;
        }
        *head = prev;
    }
    

Log in to reply
 

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