0369. Plus One Linked List

https://leetcode.com/problems/plus-one-linked-list

Description

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

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

Example 1:

**Input:** head = [1,2,3]
**Output:** [1,2,4]

Example 2:

**Input:** head = [0]
**Output:** [1]

Constraints:

• The number of nodes in the linked list is in the range [1, 100].

• 0 <= Node.val <= 9

• The number represented by the linked list does not contain leading zeros except for the zero itself.

ac1: recursive

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode plusOne(ListNode head) {
        boolean hasCarry = helper(head);

        if (hasCarry) {
            ListNode h = new ListNode(1);
            h.next = head;
            return h;
        }

        return head;
    }

    private boolean helper(ListNode node) {
        // exit
        if (node == null) return true;

        boolean hasCarry = helper(node.next);
        if (hasCarry) {
            if (node.val == 9) {
                node.val = 0;
                return true;
            } else {
                node.val++;
                return false;
            }
        }

        return false;
    }
}

ac2: iterative

This one is really smart, but it's not a general solution, only suitable for this one.

/**
 * 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;
        ListNode firstNot9 = dummy, r = head;

        while (r != null) {
            if (r.val < 9) firstNot9 = r;
            r = r.next;
        }

        firstNot9.val++;
        r = firstNot9.next;
        while (r != null) {
            r.val = 0;
            r = r.next;
        }

        return dummy.val == 1 ? dummy : dummy.next;
    }
}