描述

给定一个用单链表表示的整数，然后把这个整数加一。
数据范围：链表长度满足  ，链表上每个节点的值满足  ，可以保证链表在非 0 的情况下没有前导零
问题分析：其实这个跟数租加一一样，同样从后往前逐个检查当前值是否为9，是9就重置为0，否则直接当前值+1，退出循环。
只不过数租可以通过下标直接从后往前，而链表不能从后往前，那么我们可以反转链表，然后从前往后逐个判断是否为9。操作同数租。
值得注意的是p->next=NULL这个特殊的节点，因为如果直到最后都满足条件，p=p->next，p就指向了NULL。显然不行。
所以我们循环条件里面就限定p->next!=NULL。然后再判断当循环到最后一个节点时该节点的值是否为9，不为9，直接当前值+1，否则
让当前节点值为0，然后创建一个新节点让该节点的值为1，且下一个指向null。
结束上述操作后，再反转一次链表。具体过程看下面代码:
复杂度分析：
时间复杂度O(n)：两次旋转链表O(n)，往链表+1，最坏情况O(n)。
空间复杂度O(1)：只定义了两个变量。 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        head=reverse(head);
        ListNode* p=head;
        while(p->next!=NULL&&p->val==9){
            p->val=0;
            p=p->next;
        }
        if(p->next!=NULL||(p->next==NULL&&p->val!=9)) p->val+=1;
        else {//当循环到最后一个节点且该节点值为9，表示有进位，需要创建一个新节点
            ListNode *l=(ListNode*)malloc(sizeof(ListNode));
            l->val=1;
            l->next=NULL;
            p->val=0;
            p->next=l;
        }
        head=reverse(head);
        return head;
    }
    ListNode* reverse(ListNode* head){
        ListNode *p=NULL;
        ListNode *q=NULL;
        while(head!=NULL){
            p=head;
            head=head->next;
            p->next=q;
            q=p;
        }
        return q;
    }
};