Description
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.
给定一个非负整数，这个整数表示为一个非空的单链表，每个节点表示这个整数的一位。返回这个整数加一。
除了0本身，所有数字在最高位前都没有0。
列表的头节点存的是这个整数的最高位。
Examples
Input: 1 -> 2 -> 3 -> null
Output: 1 -> 2 -> 4 -> null
Explanation:
123 + 1 = 124
Input: 9 -> 9 -> null
Output: 1 -> 0 -> 0 -> null
Explanation:
99 + 1 = 100
Answer
Using 2 pointers to traverse the list. One is to go through the whole list and the other one is to record the location of the last none-9 value node. If all the nodes which not in the end of the list have value which is not 9, then the last node’s value needs to plus one. If not, then let the last none-9 node’s value plus one and place all the values of the rest nodes to 0.
Time Complexity
O(n).
Code
C++
class Solution {
public:
ListNode * plusOne(ListNode * head) {
if(!head) return head;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* l = dummy;
ListNode* cur = dummy;
while(cur->next)
{
cur = cur->next;
if(cur->val != 9) l = cur;
}
if(cur->val != 9)
cur->val++;
else
{
l->val++;
while(l->next)
{
l = l->next;
l->val = 0;
}
}
if(dummy->val == 0) return dummy->next;
return dummy;
}
};
