369 Plus One Linked List

1. Question

Given a non-negative integer represented asnon-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:
1
Input:
2
1->2->3
3
4
Output:
5
1->2->4
Copied!

2. Implementation

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
class Solution {
10
public ListNode plusOne(ListNode head) {
11
ListNode dummy = new ListNode(0);
12
dummy.next = head;
13
14
ListNode lastNotNine = dummy, curNode = head;
15
16
while (curNode != null) {
17
if (curNode.val != 9) {
18
lastNotNine = curNode;
19
}
20
curNode = curNode.next;
21
}
22
23
lastNotNine.val += 1;
24
curNode = lastNotNine.next;
25
26
while (curNode != null) {
27
curNode.val = 0;
28
curNode = curNode.next;
29
}
30
return dummy.val == 1 ? dummy : dummy.next;
31
}
32
}
Copied!

3. Time & Space Complexity

时间复杂度: O(n), 空间复杂度: O(1)