题意理解

用链表表示一个数字，把该数字加1，再用链表的格式输出。

方法一

递归
因为这里是单向链表，且最低位在链表的尾端。如果指针遍历到链表尾端做加法后，处理进位时无法向前传递。所以考虑使用递归的方法，cal()函数返回这一位上产生的进位。

在该函数中，我们先通过递归调用获得前一位产生的进位，然后计算本位上会产生的进位，最后计算本位在加法计算后的值。注意这里的顺序不能改变。最低位需要加1，我们单独处理。同时，如果最高位产生了进位，我们还需要在链表的头前面再加上一个节点。

递归调用的示意图如下：

具体代码如下：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    int sum(ListNode* p){
        //最低位特殊处理，是加1
        if (p->next == NULL)
        {
            p->val = (p->val + 1)%10;
            if (!p->val) return 1;
            else return 0;
        }
        int jinwei = sum(p->next);
        int nextjinwei = (p->val + jinwei)/10;
        p->val = (p->val + jinwei)%10;
        return nextjinwei;
    }
    
    ListNode* plusOne(ListNode* head) {
        // write code here
        int jinwei = sum(head);
        //看最高位是否还要进位
        if (jinwei == 1)
        {
            ListNode *p = new ListNode(1);
            p->next = head;
            head = p;
        }
        return head;
    }
};

时间复杂度： $O(N)O(N)$。递归过程中单项链表的每一个节点遍历了一次。
空间复杂度： $O(N)O(N)$。递归产生的递归栈的深度为N。

方法二

转换
把链表中的数字转换为数组格式，对数组的最后一位加1，并依次向前进位更新。

具体代码如下：

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    
    
    ListNode* plusOne(ListNode* head) {
        // write code here
        vector<int> number;
        ListNode *p = head;
        //转化为数组形式
        while (p!=NULL)
        {
            number.push_back(p->val);
            p = p->next;
        }
        //处理加1计算
        int i = number.size()-1;
        int jinwei = (number[i] + 1)/10;
        number[i] = (number[i] + 1)%10;
        i--;
        while (jinwei && i>=0)
        {
            number[i] = (number[i] + jinwei)%10;
            if (!number[i]) jinwei = 1;
            else jinwei = 0;
            i--;
        }
        if (jinwei) number.insert(number.begin(), 1);
        //转换为单向链表形式
        for (i=0;i<number.size();i++)
        {
            ListNode *node = new ListNode(number[i]);
            if (p!=NULL) p->next = node;
            p = node;
            if (!i) head = p;
        }
        return head;
    }
};

时间复杂度： $O(N)O(N)$。单项链表的每一个节点遍历了一次，数组number遍历了两次。
空间复杂度： $O(N)O(N)$。开辟了新的数组，长度为N；以及新的链表，长度也为N。