Plus One Linked List

Description

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

Hint

Train of Thought

找到最后一个不为9的数字, 如果这个数字就是末尾, 就加1.
如果不是, 它后面肯定全是9, 把当前点加1, 后面的全变为0
再考虑会不会进位

Code

public class Solution {
    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;
    }
}

Complexity