给你一个 非空 链表的头节点 head ，表示一个不含前导零的非负数整数。

将链表 翻倍 后，返回头节点 head 。

 

示例 1：

输入：head = [1,8,9]
输出：[3,7,8]
解释：上图中给出的链表，表示数字 189 。返回的链表表示数字 189 * 2 = 378 。

示例 2：

输入：head = [9,9,9]
输出：[1,9,9,8]
解释：上图中给出的链表，表示数字 999 。返回的链表表示数字 999 * 2 = 1998 。

 

提示：

• 链表中节点的数目在范围 [1, 104] 内
• 0 <= Node.val <= 9
• 生成的输入满足：链表表示一个不含前导零的数字，除了数字 0 本身。

C++

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* doubleIt(ListNode* head) {
        vector<int> vec;
        ListNode* p=head;
        while(p) {
            vec.push_back(p->val);
            p=p->next;
        }
        int n=vec.size();
        int i=n-1;
        int mod=0;
        while(i>=0) {
            int tmp=vec[i]*2+mod;
            vec[i]=tmp%10;
            mod=tmp/10;
            i--;
        }
        ListNode* pre=new ListNode(mod);
        pre->next=head;
        p=head;
        i=0;
        while(p && i<n) {
            p->val=vec[i];
            p=p->next;
            i++;
        }
        if(mod==0) {
            pre=pre->next;
        }
        return pre;
    }
};