```
public class Solution {
public ListNode plusOne(ListNode head) {
ListNode fake = new ListNode(0); // put fake head in the beginning
fake.next = head;
boolean fakeHead = false; // fake head will be new header or not.
ListNode p = fake;
ListNode q = head;
while(q!=null){
if(q.val != 9) p = q; //find the first non-9 to be p
q = q.next;
}
if(p == fake) fakeHead = true;
//find p is still in the fake position, then fake will be the new head
while(p!=null){
if(p.val != 9)
p.val++; //change the first non-9(if fakeHead == true, this is fakeHead's 0) to be ++ number
else p.val = 0; // change the rest 9 to 0.
p = p.next;
}
if(fakeHead) return fake; // fakeHead is new head
else return head; // head is still head
}
```

}

Time complexity is O(N), space is O(1)