# Iterative Two-Pointers with dummy node Java O(n) time, O(1) space

• ``````public class Solution {
ListNode dummy = new ListNode(0);
ListNode i = dummy;
ListNode j = dummy;

while (j.next != null) {
j = j.next;
if (j.val != 9) {
i = j;
}
}

if (j.val != 9) {
j.val++;
} else {
i.val++;
i = i.next;
while (i != null) {
i.val = 0;
i = i.next;
}
}

if (dummy.val == 0) {
return dummy.next;
}

return dummy;
}
}
``````
• i stands for the most significant digit that is going to be incremented if there exists a carry
• dummy node can handle cases such as "9->9>-9" automatically

• Nice solution. Simplified a little bit.

``````public class Solution {
ListNode dummy = new ListNode(0);
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;
}
}
``````

• This post is deleted!

• Good solution. Try to explain with example 1->8->9->7->9->9.
Pointer i points to the first node before the tailing 9s, which is 7 in this case and pointer j points to the last node of the whole list, which is 9.

1. If the value of j equals to 9, the sublist behind i should be updated. Increments the value of 1 by 1 and set the following nodes to be 0.
2. If the value of j is not 9, just increments j.val by one.

The use of dummy node:

1. In the cases like 9->9->9, the answer should return dummy. (1->0->0->0)
2. In other cases like 8->9->9, the answer should return dummy.next. (0->9->0->0, dummy is the first 0).

• @ocean you don't need j, i is enough. When "if (j.val != 9) ", i is equal to j.

• Very nice solution. Especially the use of dummy head.
Note the invariant which help we think and code correctly. Thanks for sharing!

``````    public ListNode plusOne(ListNode head) {
ListNode dmy = new ListNode(0), lastNot9 = dmy;
for (ListNode n = head; n != null; n = n.next) {
if (n.val != 9) lastNot9 = n; /* invariant: [lastNot9.next, tail] are all 9*/
}
lastNot9.val++;
for (ListNode n = lastNot9.next; n != null; n = n.next) {
n.val = 0;
}
return dmy.val == 1 ? dmy : head;
}
``````

• For example: 8->7->9->9
The lastNotNine is 7.
7 + 1 = 8
9 change to 0.
We got 0->8->8->0->0
return dummy.next

For example: 9->9->9
The lastNotNine is 0.
0 + 1 = 1
9 change to 0.
We got 1->0->0->0
return dummy

``````public class Solution {
ListNode dummy = new ListNode(0);
ListNode lastNotNine = dummy;
while(node != null){
if(node.val != 9){
lastNotNine = node;
}
node = node.next;
}

lastNotNine.val = lastNotNine.val + 1;
lastNotNine = lastNotNine.next;
while(lastNotNine != null){
lastNotNine.val = 0;
lastNotNine = lastNotNine.next;
}
return dummy.val == 1 ? dummy : dummy.next;
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.