369. Plus One Linked List

Given a non-negative integer represented as a linked list of digits, plus one to the integer.

The digits are stored such that the most significant digit is at the head of the list.

• recursive solution

c++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    int solution(ListNode* node) {
        if(!node) return 1;
        int append = solution(node->next);
        node->val += append;
        if(node->val == 10) {
            node->val = 0;
            return 1;
        }
        return 0;
    }
public:
    ListNode* plusOne(ListNode* head) {
        int append = solution(head);
        if(append)
            head = new ListNode(1, head);
        return head;
    }
};

• iterative solution

c++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        ListNode* node = head;
        vector<ListNode*> st;
        while(node) {
            st.push_back(node);
            node = node->next;
        }
        int append = 1;
        while(!st.empty() && append) {
            st.back()->val += append;
            if(st.back()->val == 10) {
                st.back()->val = 0;
                append = 1;
            } else append = 0;
            st.pop_back();
        }
        
        if(append)
            head = new ListNode(1, head);
        return head;
    }
};