Given a non-negative integer represented as non-empty a singly linked list of digits, plus one to the integer.

You may assume the integer do not contain any leading zero, except the number 0 itself.

The digits are stored such that the most significant digit is at the head of the list.

Example:

Input:
1->2->3

Output:
1->2->4

一刷
题解：
用递归来寻找最底层是否要进位

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode plusOne(ListNode head) {
        if(head == null) return head;
        if(exceed(head.next) || head.next == null){
            if(head.val == 9){
                ListNode newHead = new ListNode(1);
                newHead.next = head;
                head.val = 0;
                return newHead;
            }else{
                head.val++;
                return head;
            }
        }else{
            return head;
        }
    }
    
    private boolean exceed(ListNode node){
        if(node == null) return false;
        if(node.next == null || exceed(node.next)){
            if(node.val == 9){
                node.val = 0;
                return true;
            }else{
                node.val++;
                return false;
            }
        }
        return false;
    }
}

二刷
简化写法：

/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
   public ListNode plusOne(ListNode head) {
       ListNode Dummy = new ListNode(0);
       Dummy.next = head;
       if(helper(head)){
           Dummy.val++;
           return Dummy;
       }else{
           return head;
       }
   }
   
   private boolean helper(ListNode node){
       if(node == null) return true;
       
       if(helper(node.next)){
           if(node.val == 9 ){
               node.val = 0;
               return true;
           }
           node.val++;
       }
       
       return false;
   }
}