369. 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

方法1：Reverse -> Plus one -> Reverse

很直观的方法，先Reverse原链表，再加1，有进位的话保留，最后再Reverse一次

代码如下:

public ListNode plusOne(ListNode head) {
    head = reverse(head);
    int carry = 1;
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    while (carry != 0 && dummy.next != null) {
        carry = (dummy.next.val + 1) / 10;
        dummy.next.val = (dummy.next.val + 1) % 10;
        dummy = dummy.next;
    }
    if (carry != 0)
        dummy.next = new ListNode(carry);
    return reverse(head);
}
public ListNode reverse(ListNode head) {
    ListNode dummy = new ListNode(0);
    while (head != null) {
        ListNode next = dummy.next;
        dummy.next = head;
        head = head.next;
        dummy.next.next = next;
    }
    return dummy.next;
}

方法2：找最后一个不是9的Node

找到最后一个不是9的数，给其+1，此数后面全是0.

public ListNode plusOne(ListNode head) {
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode lastNotNine = dummy, node = head;
    while (node != null) {
        if (node.val != 9) {
            lastNotNine = node;
        }
        node = node.next;
    }
    
    lastNotNine.val++;
    node = lastNotNine.next;
    while (node != null) {
        node.val = 0;
        node = node.next;
    }
    return dummy.val == 1 ? dummy : dummy.next;
}

方法3：递归

public ListNode plusOne(ListNode head) {
    if (head == null)
        return new ListNode(1);
    ListNode plused = plusOne(head.next);
    if (plused != head.next)
        head.val++;
    if (head.val <= 9)
        return head;
    head.val = 0;
    plused.next = head;
    return plused;
}

public ListNode plusOne(ListNode head) {
    if (head == null) {
        return new ListNode(1);
    }
    ListNode res = new ListNode(1);
    res.next = head;
    return helper(head) > 0 ? res : head;
}
public int helper(ListNode head) {
    int sum = head.val + (head.next == null ? 1 : helper(head.next));
    head.val = sum % 10;
    return sum / 10;
}

Ref: