lintcode904. 加一链表

朱雀 2023-07-25 05:28 124阅读 0赞

给定一个非负整数，这个整数表示为一个非空的单链表，每个节点表示这个整数的一位。返回这个整数加一。  
除了0本身，所有数字在最高位前都没有0。  
列表的头节点存的是这个整数的最高位。

样例
    样例1
    
    输入: 1 -> 2 -> 3 -> null
    输出: 1 -> 2 -> 4 -> null
    解释:
    123 + 1 = 124
    样例2
    
    输入: 9 -> 9 -> null
    输出: 1 -> 0 -> 0 -> null
    解释:
    99 + 1 = 100

* Definition of singly-linked-list:
     * class ListNode {
        
     * public:
     *     int val;
     *     ListNode *next;
     *     ListNode(int val) {
        
     *        this->val = val;
     *        this->next = NULL;
     *     }
     * }
     */
    
    class Solution {
        
    public:
        /**
         * @param head: the first Node
         * @return: the answer after plus one
         */
        ListNode * plusOne(ListNode * head) {
        
            // Write your code here
            string num="";
            dfs(head,num);
            if(num!="")//在99+1=100这种情况下，要增加一个头结点
            {
        
                ListNode *newhead=new ListNode(num[0]-'0');
                newhead->next=head;
                return newhead;
            }
            return head;
        }
        string addone(string num)//实现字符串加一
        {
        
            int index=num.size()-1;
            int cf=0;
            while(index>=0)
            {
        
                if(num[index]=='9') 
                {
        
                    num[index]='0';
                    cf=1;
                }
                else
                {
        
                    num[index]=num[index]+1;
                    cf=0;
                    break;
                }
                index--;
            }
            if(cf==1) num.insert(num.begin(),'1');
            return num;
        }
        void dfs(ListNode *head,string &num)//深度搜索并改变加一后的数值
        {
        
            if(head==NULL)
            {
        
                num=addone(num);
                return;
            }
            else 
            {
        
                num+='0'+head->val;
                dfs(head->next,num);
                head->val=num[num.size()-1]-'0';
                num.erase(num.end()-1);
                return;
            }
        }
    };