Reference: 66. Plus One / 369. Plus One Linked List
Difficulty: Easy

My Post: Java Recursive Solution with Comments

Just show me the code!

66. Plus One

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// no need to use list
// no easy way to convert int[] to Integer list, or Integer list to int[]
public int[] plusOne(int[] digits) {
int n = digits.length;
int carry = 1;
for (int i = n - 1; i >= 0; --i) {
int sum = digits[i] + carry;
digits[i] = sum % 10;
carry = sum / 10;
}
if (carry > 0) { // need to expand the array
int[] newDigits = new int[n + 1];
System.arraycopy(digits, 0, newDigits, 1, n);
newDigits[0] = carry;
digits = newDigits;
}
return digits;
}

Time: $O(N)$
Space: $O(1)$ or $O(N)$

369. Plus One Linked List

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
* Recursion
*/
public ListNode plusOne(ListNode head) {
// Solve it recursively
int carry = plusOneHelper(head);
if (carry > 0) { // need to expand the linked list (add one more node)
ListNode newNode = new ListNode(carry);
newNode.next = head;
head = newNode;
}
return head;
}

// return carry
// 1 -> 2 -> 3 -> null
// head
private int plusOneHelper(ListNode head) {
if (head == null) {
return 1; // plus one
}
int carry = plusOneHelper(head.next);
int sum = head.val + carry;
head.val = sum % 10; // update node
return sum / 10;
}

Time: $O(N)$
Space: $O(N)$


Comment