题目大意：
给单链表加一
用一个 非空 单链表来表示一个非负整数，然后将这个整数加一。
你可以假设这个整数除了 0 本身，没有任何前导的 0。
这个整数的各个数位按照 高位在链表头部、低位在链表尾部 的顺序排列。
示例：
输入: [1,2,3] 输出: [1,2,4]
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=369
解题思路分析：
遇到链表题肯定要用上递归思路，利用本题给出的head节点，一路递归到最未节点，先将其val加一，如果val小于10，直接将加一后的数值保存至节点。如果val等于10，这时出现进位，当前节点值为0，进位1，我们将进位作为返回值返回给上一层递归函数。在上层递归函数中，我们先查看下层递归函数的返回值（进位），将其累加到自身，如果等于10，依然需要进位，继续返回1给更上层的递归函数。
注意一点，当递归结束时，进位依然是1，那么我们需要新建一个头结点，将其赋值为1，然后再将原先的头结点加入到其后方即可。比如输入[9, 9]，加一后的输出应该是[1, 0, 0]。
public ListNode plusOne(ListNode head) {
int carry=help(head); // 递归求解
if(carry==0) return head; // 如果进位为0，直接返回head
// 如果进位为1，新建一个头结点
ListNode node = new ListNode(1);
// 将原先的头结点连接到新建节点后方
node.next=head;
return node;
}
// 递归函数，返回值为进位数
int help(ListNode head){
// 如果头为空，返回0
if(head==null) return 0;
// 当前节点值
int val=head.val;
// 如果当前节点为末尾结点，值加一
if(head.next==null) val+=1;
// 递归取得后一节点的进位数
int carry=help(head.next);
// 当前节点的值加上进位数
val += carry;
// 如果当前节点值为10，需要进位
if(val==10){
// 当前值为0
head.val = 0;
// 进位1
return 1;
}else{
// 当前值不变
head.val = val;
// 进位0
return 0;
}
} 本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Plus One Linked List.
Memory Usage: 34.5 MB, less than 100.00% of Java online submissions for Plus One Linked List.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-369-plus-one-linked-list-解题思路分析/