题意：
        给定一个用单链表表示的整数，然后把这个整数加一。

方法一：
逆向模拟相加

思路：

步骤如下：
        首先，反转链表；
        然后，遍历链表+1；
        之后，判断最高进位是否要添加新的节点；
        最后，再次反转链表。



class Solution {
public:
    
    ListNode* plusOne(ListNode* head) {
        if(head==nullptr)
            return head;
        //反转字符串
        head=reverseList(head);
        
        int flag=1;
        ListNode *p=head;
        while(p){//遍历链表+1
            int t=p->val+flag;
            p->val=t%10;
            if(t>=10){
                flag=1;
            }else{
                flag=0;
                break;
            }
            p=p->next;
        }
        if(flag){//最后判断进位
            p=head;
            while(p->next){
                p=p->next;
            }
            ListNode *q=new ListNode(1);
            p->next=q;
        }
        
        //反转字符串
        head=reverseList(head);
        return head;
    }
    
    ListNode* reverseList(ListNode* head){//反转字符串
        ListNode* p=head,*q=head->next,*t;
        p->next=nullptr;
        while(q){
            t=q->next;
            q->next=p;//逆转效果
            p=q;
            q=t;
        }
        return p;
    }
};

时间复杂度：
空间复杂度：

方法二：
字符串存储

思路：
        首先，用字符串存储链表的值；
        然后，利用字符串进行+1操作；
        最后，将字符串的值替换给原链表。
        注意：根据最后进位判断是否要添加一个新节点。        


class Solution {
public:
    
    ListNode* plusOne(ListNode* head) {
        if(head==nullptr)
            return head;
        
        string s="";//初始化字符串
        ListNode *p=head;
        while(p){//遍历链表追加字符串
            s+=p->val+'0';
            p=p->next;
        }
        int flag=1;
        for(int i=s.size()-1;i>=0;i--){
            int t=s[i]-'0'+flag;//加法运算
            s[i]=t%10+'0';
            if(t>=10){
                flag=1;
            }else{
                flag=0;
                break;
            }
        }
        
        p=head;
        int i=0;
        while(p){//遍历链表替换值
            p->val=s[i]-'0';
            p=p->next;
            i++;
        }
        if(flag){//最后判断进位
            ListNode *q=new ListNode(1);
            q->next=head;
            head=q;
        }
        
        return head;
    }
};


时间复杂度：
空间复杂度：