Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.
You may assume the integer do not contain any leading zero, except the number 0 itself.
The digits are stored such that the most significant digit is at the head of the list.
Example :
Input: [1,2,3] Output: [1,2,4]
A:
核心技巧就是加了一个 dummy header, 然后递归调用
/** * 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* plusOne(ListNode* head) { ListNode * dummy = new ListNode(0); dummy->next = head; helper(dummy); if(dummy->val == 1){ return dummy; }else{ delete dummy; return head; } } private: bool helper(ListNode* head){ if(not head->next){ int carry = (head->val + 1) /10; head->val = (head->val + 1) % 10; return carry ==1; }else{ bool hasCarry = helper(head->next); if(hasCarry){ int carry = (head->val + 1) /10; head->val = (head->val + 1) % 10; return carry ==1; }else{ return false; } } } };
No comments:
Post a Comment