Given a non-negative integer represented asnon-emptya 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.
您在真实的面试中是否遇到过这个题？
Yes
样例
Given head =1 -> 2 -> 3 -> null, return1 -> 2 -> 4 -> null.
/**
* 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
ListNode *a;
ListNode *p,*r,*o,*b;
p = head;
r = head->next;
//*a= ListNode(0);
//如果只有一位
if(head->next == NULL){
if(head->val == 9){
ListNode *a= new ListNode(0);
head->next = a;
head->val = 1;
return head;
}else{
head->val += 1;
return head;
}
}
//如果全是9
head = p;
while(head->val == 9){
if(head->next != NULL){
head = head->next;
}else{
ListNode *a= new ListNode(0);
head = p;
head->val = 1;
head = head->next;
while(true){
head->val =0;
if(head->next==NULL){
head->next = a;
return p;
}else{
head= head->next;
}
}
return head;
}
}
//正常
while(true){
head = r;
if(r->next == NULL){
break;
}
r = r->next;
}
//将head指向最后
if(r->val == 9){
while(head->val == 9){
o = p;
while(o->next != head){
o = o->next;
}
head = o;
}
o = head->next;
head->val +=1;
r= head->next;
while(true){
r->val = 0;
if(r->next == NULL){
return p;
}else{
r = r->next;
}
}
}else{
r->val +=1;
}
return p;
}
};
