给单链表加一：

思路：

1.先建立一个虚的头结点，将头结点连接到原链表的头结点

2.注意头结点的值要初始化为0！！！

3.由于需要判断当前的节点的值是否需要加1，就需要知道后面的节点的值是否会产生进位

4.所以用递归的思想，先得到后面的节点的值

5.分为两种情况：如果后面没有节点，就表明该链表只有一个节点，所以将该节点的值加1就直接可以返回了

6.否则就将通过递归返回返回下一个节点的值，进行判断，如果下一个节点的值等于10，就将现在的节点的值加1，将后面的这个节点的值改为0

7.最后判断一下是否会产生一个最高位，如果虚节点的值不为0，就返回虚节点的值，否则就返回原先的链表的头结点

代码：

import java.util.*;

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

public class Solution {
    public ListNode Plusnode(ListNode head){
        //特殊情况判断：如果发现当前节点的后面并不存在节点
        //那么就表明当前的节点就是链表（由于该链表只有一位）的最后一位，将该位加1即可，就可以结束了
        if(head.next==null){
            head.val+=1;
            return head;
        }
        //否则就需要通过递归先得到后面的那个节点
        ListNode next= Plusnode(head.next);
        //进行判断后面的节点的值是否会产生进位
        //如果之前的这个节点会产生进位，就将前面的这一位的值变为0
        //将当前节点的值加1
        if(next.val==10){
            next.val=0;
            head.val+=1;
        }
        return head;

    }
    public ListNode plusOne (ListNode head) {
        //创建一个虚的头结点，将虚的头结点连接在原链表的头结点：注意一定要初始化为0！！！
        //因为到时候可能会有进位
        ListNode newhead=new ListNode(0);
        newhead.next=head;
        //因为想要判断当前节点的值是否需要加一，需要先得到之前的一个节点的值是否会产生进位
        Plusnode(newhead);
        //判断一下如果虚的头结点的值不是0，就返回虚节点，否则就表示加1后不会使得数增加一位
        return newhead.val==0?head:newhead;
    }
}