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

My Solutions:

1。 方法1

• 反转链表

• +1 运算

• 再次反转

//pseudo code

ListNode head2 = reverse(head);

ListNode node = head2;
while (node != null) {
    if (node.val + 1 <= 9) {
        node.val = node.val + 1；
        break; 
    } else {
        node.val = 0;
        if (node.next == null) {
            node.next = new ListNode(1);
            break;
        } else {
            node = node.next;
        }
    }
}
return reverse(head2);

2。 方法2：不反转

遍历链表，找到右起第一个不为9的数字

• 找到？此数字+1，把后面所有的node变成0

• 找不到？说明所有数字均为9。在表头新建一个值为0的新节点，进行加1处理，然后把右边所有的数字都置为0即可。

举例来说：

• 1->2->3: 第一个不为9的数字为3，对3进行加1，变成4，右边没有节点了，所以不做处理，返回1-> 2->4。

• 8->9->9: 第一个不为9的数字为8，进行加1处理变成了9，然后把后面的数字都置0，得到结果9->0 -->0。

• 9->9->9: 找不到不为9的数字，那么在前面新建一个值为0的节点，进行加1处理变成了1，把后面的数字都置0，得到1->0->0->0。