AlgoPressAppearance
0369-给单链表加一
https://leetcode.cn/problems/plus-one-linked-list
用一个 非空 单链表来表示一个非负整数，然后将这个整数加一。
你可以假设这个整数除了 0 本身，没有任何前导的 0。
这个整数的各个数位按照 高位在链表头部、低位在链表尾部的顺序排列。
示例:
输入: [1,2,3] 输出: [1,2,4]
思路
因为链表只能往后计算，所有有进位的时候比较难处理，使用 pre 表示前置节点的话，再产生进位还是不好处理。 可以考虑将链表反转，然后从1第一个加1，有进位则往后计算 next 节点 最后再反序输出链表
参考代码
csharp
public class Solution {
private ListNode Reverse(ListNode head){
ListNode pre = null;
ListNode cur = head;
while(cur.next != null){
ListNode temp = cur;
cur = cur.next;
temp.next = pre;
pre = temp;
}
cur.next = pre;
return cur;
}
public ListNode PlusOne(ListNode head) {
ListNode rev = Reverse(head);
//加1
ListNode cur = rev;
int carry = 1;
while(carry > 0){
int sum = cur.val + 1;
cur.val = sum % 10;
if(sum == 10){ //有进位
if(cur.next != null){
cur = cur.next;
carry = 1;
}
else{//最后一位
cur.next = new ListNode(1);
carry = 0;
}
}
else{
carry = 0;
}
}
//最后再翻转输出
return Reverse(rev);
}
}
思路2：官方
找到最右的第一个非9数字加一，然后剩下的9都变成0 为了保证第一个节点，可以处理进位，添加一个 dummyHead
csharp
public class Solution {
public ListNode PlusOne(ListNode head) {
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
//从前往后找到最后一个非9数字
ListNode nodeNotNine = dummyHead;
ListNode cur = dummyHead;
while(cur!=null){
if(cur.val != 9){
nodeNotNine = cur;
}
cur = cur.next;
}
//设置
nodeNotNine.val++;
cur = nodeNotNine.next;
while(cur != null){
cur.val = 0;
cur = cur.next;
}
return dummyHead.val == 0 ? dummyHead.next : dummyHead;
}
}
复习：20220614
csharp
public class Solution {
public ListNode PlusOne(ListNode head) {
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode pre = dummyHead;
ListNode cur = dummyHead;
while(cur != null){
if(cur.val != 9){
pre = cur;
}
cur = cur.next;
}
pre.val += 1;
cur = pre.next;
while(cur != null){
cur.val = 0;
cur = cur.next;
}
return dummyHead.val == 0 ? dummyHead.next : dummyHead;
}
}