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

Solution1：遞歸 (回傳進位)

思路： 遞歸來達到從后面處理的效果，post處理回傳進位。
實現(xiàn)1a/1b: 創(chuàng)建dummy or not (basically same)
Time Complexity: O(N) Space Complexity: O(N) 遞歸緩存

Solution2：Iterative

思路： // dummy -> 1 -> 2 -> 3 -> 9 -> 9 -> null
如果最后一位不是9，直接＋1即可；如果是9，就需要：
找到最后一個不是9的位置，＋1，然后后續(xù)都置零。
Time Complexity: O(N) Space Complexity: O(1)

Solution1 Code：

class Solution1a {
    public ListNode plusOne(ListNode head) {
        if(DFS(head) == 0) {
            return head;
        }else{
            ListNode newHead = new ListNode(1);
            newHead.next = head;
            return newHead;
        }
    }

    public int DFS(ListNode head){
        if(head == null) return 1;   // last one: plus one

        // recursion
        int carry = DFS(head.next);

        // deal with current level
        if(carry == 0) {
            return 0;
        }
        else {
            int val = head.val + carry;
            head.val = val % 10;
            return val / 10;
        }
    }
}

Solution1b Code：

class Solution1b {
    public ListNode plusOne(ListNode head) {
        
        // dummy head for potential carry;
        ListNode dummy = new ListNode(0); 
        dummy.next = head;
        
        DFS(dummy);
        if(dummy.val == 0) return dummy.next;
        else return dummy;
     
    }

    public int DFS(ListNode head){
        if(head == null) return 1;   // last one: plus one

        // recursion
        int carry = DFS(head.next);

        // deal with current level
        if(carry == 0) {
            return 0;
        }
        else {
            int val = head.val + carry;
            head.val = val % 10;
            return val / 10;
        }
    }
}

Solution2 Code：

class Solution2 {
    public ListNode plusOne(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode i = dummy; // last digit which is not 9
        ListNode j = dummy; // iterating pointer
        
        // dummy  ->  1  ->  2  ->  3  ->  9  ->  9  ->  null
        //                          i             j
        
        // find i: the last digit which is not 9
        while (j.next != null) {
            j = j.next;
            if (j.val != 9) {
                i = j;
            }
        }
        
        // if last one is not 9, then just adding one should work
        if (j.val != 9) {
            j.val++;
        // if last one is nine, then make 399 to 400
        } else {
            i.val++;
            i = i.next;
            while (i != null) {
                i.val = 0;
                i = i.next;
            }
        }
        
        // check if first digit
        if (dummy.val == 0) {
            return dummy.next;
        }
        
        return dummy;
    }
}