Plus One Linked List

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

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

The easiest way is to reverse the linked list, do the math, and reverse it back. But that requires us to go through the list three times (reverse, calculate, and reverse again). A better way is to use recursion. We first recursively get the carry from its next node, if we reach the end, we return 1, which is the number to be added. Now for every node, we return the carry it may have until the head. If we find the carry is not 0, we add a new node in front of the head and return head.

public ListNode plusOne(ListNode head){
        if (head == null) {
            return head;
        }
        int carry = getPlusOne(head);
        if (carry != 0) {
            ListNode first = new ListNode(carry);
            first.next = head;
            head = first;
        }
        return head;
    }

    private int getPlusOne(ListNode head) {
        if (head == null) {
            return 1;
        }
        int carry = getPlusOne(head.next);
        int sum = head.val + carry;
        head.val = sum % 10;
        return sum / 10;
    }