题解 | #给单链表加一#
给单链表加一
http://www.nowcoder.com/practice/a2f1105d2ac5466e9ba8fd61310ba6d1
描述
给定一个用单链表表示的整数，然后把这个整数加一。
数据范围：链表长度满足 
，链表上每个节点的值满足 
，可以保证链表在非 0 的情况下没有前导零
问题分析：其实这个跟数租加一一样，同样从后往前逐个检查当前值是否为9，是9就重置为0，否则直接当前值+1，退出循环。
只不过数租可以通过下标直接从后往前，而链表不能从后往前，那么我们可以反转链表，然后从前往后逐个判断是否为9。操作同数租。
值得注意的是p->next=NULL这个特殊的节点，因为如果直到最后都满足条件，p=p->next，p就指向了NULL。显然不行。
所以我们循环条件里面就限定p->next!=NULL。然后再判断当循环到最后一个节点时该节点的值是否为9，不为9，直接当前值+1，否则
让当前节点值为0，然后创建一个新节点让该节点的值为1，且下一个指向null。
结束上述操作后，再反转一次链表。具体过程看下面代码:
复杂度分析：
时间复杂度O(n)：两次旋转链表O(n)，往链表+1，最坏情况O(n)。
空间复杂度O(1)：只定义了两个变量。
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
ListNode* plusOne(ListNode* head) {
head=reverse(head);
ListNode* p=head;
while(p->next!=NULL&&p->val==9){
p->val=0;
p=p->next;
}
if(p->next!=NULL||(p->next==NULL&&p->val!=9)) p->val+=1;
else {//当循环到最后一个节点且该节点值为9，表示有进位，需要创建一个新节点
ListNode *l=(ListNode*)malloc(sizeof(ListNode));
l->val=1;
l->next=NULL;
p->val=0;
p->next=l;
}
head=reverse(head);
return head;
}
ListNode* reverse(ListNode* head){
ListNode *p=NULL;
ListNode *q=NULL;
while(head!=NULL){
p=head;
head=head->next;
p->next=q;
q=p;
}
return q;
}
};
查看26道真题和解析
叠纸游戏公司氛围 18人发布
