## ้ข็ฎๆ่ฟฐ

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

You may assume the integer do not contain any leading zero, except the number 0 itself.

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]``````

## ไปฃ็ 

Time: O(N) && Space: O(1)

``````/**
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode() {}
*     ListNode(int val) { this.val = val; }
*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
ListNode sentinel = new ListNode(0);
ListNode notNine = sentinel;

// find the rightmost not-nine digit
}

// increase thsi rightmost not-nine digit
notNine.val++;
notNine = notNine.next;

while (notNine != null) {
notNine.val = 0;
notNine = notNie.next;
}

return sentinel.val != 0 ? sentinel : sentinal.next;
}
}``````

### Approach #2 Recursive DFS

``````class Solution {
} else {
}
}