题解 | # 给单链表加一

我觉得可以使用递归的方式来解决该题： 当链表数量大于1时：

1. 添加一个值为0的新头节点，新头节点的next为head
2. 递归计算next节点作为链表起点+1的值
3. 计算完成后，如果next节点的值等于10，当前节点+1
4. 判断头结点是否等于0。如果等于0说明没有超出原来的节点超度，返回head；如果大于0说明超出了原有的节点长度返回新头节点。

时间复杂度：O(n) 空间复杂度：O(1)

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode plusOne (ListNode head) {
        // write code here
        ListNode newHead = new ListNode(0);
        newHead.next = head;
        plusOne2(newHead);
        return newHead.val==0?head:newHead;
    }
    
    public ListNode plusOne2 (ListNode curr) {
        // write code here
        if(curr.next == null){
            curr.val+=1;
            return curr;
        }
        ListNode next = plusOne2(curr.next);
        if(next.val==10) {
            next.val = 0;
            curr.val += 1;
        }
        return curr;
    }
}