Leetcode - Plus One Linked List

My code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode plusOne(ListNode head) {
        if (head == null) {
            return head;
        }
        
        head = reverse(head);
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode pre = dummy;
        ListNode curr = head;
        int carry = 1;
        while (curr != null) {
            int sum = curr.val + carry;
            carry = sum / 10;
            curr.val = sum % 10;
            pre = pre.next;
            curr = curr.next;
        }
        
        if (carry != 0) {
            pre.next = new ListNode(carry);
        }
        
        return reverse(head);
    }
    
    private ListNode reverse(ListNode head) {
        ListNode pre = head;
        ListNode curr = head.next;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = pre;
            pre = curr;
            curr = next;
        }
        head.next = null;
        return pre;
    }
}

我自己的想法比较简单。先reverse， 再加，再reverse回去

网上看了，recursion 的做法。我没想出来，可惜。

My code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode plusOne(ListNode head) {
        if (head == null) {
            return null;
        }
        
        if (dfs(head) == 0) {
            return head;
        }
        else {
            ListNode newHead = new ListNode(1);
            newHead.next = head;
            return newHead;
        }
    }
    
    private int dfs(ListNode head) {
        if (head == null) {
            return 1;
        }
        int ret = dfs(head.next);
        if (ret == 0) {
            return 0;
        }
        else {
            int sum = ret + head.val;
            head.val = sum % 10;
            return sum / 10;
        }
    }
}

reference:
https://discuss.leetcode.com/topic/49541/java-recursive-solution

Anyway, Good luck, Richardo! -- 09/22/2016