// no need to use list // no easy way to convert int[] to Integer list, or Integer list to int[] publicint[] 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 = newint[n + 1]; System.arraycopy(digits, 0, newDigits, 1, n); newDigits[0] = carry; digits = newDigits; } return digits; }
/** * 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 privateintplusOneHelper(ListNode head){ if (head == null) { return1; // plus one } int carry = plusOneHelper(head.next); int sum = head.val + carry; head.val = sum % 10; // update node return sum / 10; }