Description

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

Solution

Reverse list, O(n), S(1)

reverse + add + reverse

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

Tail recursion, O(n), S(n)

这种尾递归的解法挺不错的，取巧的地方是，head == null时返回1，因为原本就是要add 1.

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