题解 | #给单链表加一#

class Solution {
public:
    ListNode *reverse(ListNode *head){//逆转链表
        if(!head->next) return head;
        ListNode *p=head,*q=head->next,*r=NULL;
        while(q){
            p->next=r;
            r=p;
            p=q;
            q=q->next;
        }
        p->next=r;
        return p;
    }
    ListNode* plusOne(ListNode* head) {
        // write code here
        ListNode *h1=reverse(head),*p=h1;
        int flag=0;//flag用于判断是否需要添加新节点
        while(p){
            if(p->val+1<10){
                p->val++;
                flag=0;
                break;
            }
            else{
                p->val=0;
                p=p->next;
                flag=1;
            }
        }
        if(flag){//若最高位产生进位添加新节点
            p=h1;
            while(p->next) p=p->next;
            ListNode *q=(ListNode*)malloc(sizeof(ListNode));
            q->val=1;
            q->next=NULL;
            p->next=q;
        }
        return reverse(h1);
    }
};