後來想想才知道可以像你板大神這樣inplace
一開始是想說會不會有從最右進位到最左的case 所以就直接用stack先存
但它是*2吼 而且carry最多是1
不管怎麼樣carry都不會傳超過一個digit
剩我浪費記憶體了
ListNode* doubleIt(ListNode* head) {
stack<ListNode*> s;
while(head)
{
s.push(head);
head = head->next;
}
int carry = 0;
ListNode* pre = NULL;
while(!s.empty())
{
ListNode* cur = s.top();
s.pop();
if(cur->val*2 + carry >= 10)
{
cur->val = cur->val*2 + carry - 10;
carry = 1;
}
else
{
cur->val = cur->val*2 + carry;
carry = 0;
}
cur->next = pre;
pre = cur;
}
ListNode *dummy = new ListNode(1);
dummy->next = pre;
return carry == 1 ? dummy : dummy->next;
}