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)$