## Question

Given a non-negative integer represented as non-emptya 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
``````

## Thought Process

1. To List and Back
1. Time complexity O(n)
2. Space complexity O(n)
2. Prepend node
1. Add a dummy node in the front
2. Time complexity O(n)
3. Space complexity O(1)

## Solution

``````class Solution {
List<Integer> nums = new ArrayList<>();
while (cur != null) {
cur = cur.next;
}
boolean carry = false;
for (int i = nums.size() - 1; i >= 0; i--) {
if (nums.get(i) < 9) {
nums.set(i, nums.get(i) + 1);
carry = false;
break;
} else {
nums.set(i, 0);
carry = true;
}
}
ListNode dummy = new ListNode(-1);
if (carry) {
dummy.next = new ListNode(1);
} else {
}
for (int num : nums) {
}
return dummy.next;
}
}
``````
``````class Solution {
ListNode dummy = new ListNode(0);
ListNode beforeNine = dummy, lastNode = dummy;
while (lastNode.next != null) {
lastNode = lastNode.next;
if (lastNode.val != 9) {
beforeNine = lastNode;
}
}
beforeNine.val++;
while (beforeNine.next != null) {
beforeNine = beforeNine.next;
beforeNine.val = 0;
}
return dummy.val == 0 ? dummy.next : dummy;
}
}
``````