题解 | #给单链表加一#

典型的递归

/**
 * struct ListNode {
 *    int val;
 *    struct ListNode *next;
 *    ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    int sum(ListNode *p){    //计算p节点的值，并且返回值是进位值
        if(p -> next == nullptr){    //若p节点是尾节点
            p -> val = ( p -> val + 1 ) % 10;    //计算当前位
            if(!p -> val) return 1;    //产生进位，返回1
            else return 0;    //没有进位，返回0
        }
        //若p不是尾节点，
        int ret = sum(p -> next);    //ret保存p->next传上来的进位
        int nextret = (p -> val + ret) / 10;    //计算p要往上传递的进位值
        p -> val = (p -> val + ret) % 10;    //计算p当前节点内的值
        return nextret;    //返回p要往上传递的进位值
    } 
    ListNode* plusOne(ListNode* head) {
        int ret = sum(head);    //计算head的进位，会层层往下递归，最后返回head的进位
        if(ret == 1){    //若产生了进位。则要新建一个头节点，头插法插入链表
            ListNode *p = new ListNode(1);
            p -> next = head;
            head = p;
        }
        return head;
    }
};