No recursion, no reversal, simple maths, 3ms C++


  • 1
    V

    The concept here is to find farthest point from head which can accommodate increment without carry. Rest all list is converted to 0.

    ListNode* plusOne(ListNode* head) {
            if (!head)
                return head;
            ListNode *curr = head, *lessNode = NULL;
            while (curr) {
                if (curr->val < 9)
                    lessNode = curr;
                curr = curr->next;
            }
            if (lessNode) {
                lessNode->val++;
                while (lessNode->next) {
                    lessNode->next->val = 0;
                    lessNode = lessNode->next;
                }
                return head;
            }
            else {
                ListNode* newNode = new ListNode(1);
                newNode->next = head;
                while (head) {
                    head->val = 0;
                    head = head->next;
                }
                return newNode;
            }
        }
    

Log in to reply
 

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