I came up with 2 simple approaches:

- everse the list, apply list addition, and reverse back
- more optimization: identify the rightmost node whose value is not 9.

that is: all nodes to its right have val=9. therefore, we will bump the

value of this right node and set all the vals to right to 0 after

addition.

In both cases, must consider overflow; add an additional node if needed.

Solution I:

```
public ListNode plusOne(ListNode head) {
ListNode rd = reverse(head);
int carry = 1;
ListNode node = rd.next, tail = null;
while (node != null) {
tail = node;
int sum = node.val + carry;
node.val = sum % 10;
carry = sum / 10;
if (carry == 0)
break;
node = node.next;
}
if (carry > 0)
tail.next = new ListNode(carry);
return reverse(rd.next).next;
}
private ListNode reverse(ListNode head) {
ListNode rd = new ListNode(0), node = head;
while (node != null) {
ListNode next = node.next;
node.next = rd.next;
rd.next = node;
node = next;
}
return rd;
}
```

Solution II:

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