Java elegant backtracking O(n) time O(n) stack space with comments


  • 2

    No extra space is allocated except for the stack space for recursive calls
    .No need to reverse the linked list or change its next pointer, the structure of the list might be immutable.

       public class Solution {
            public ListNode plusOne(ListNode head) {
                if (plusOneHelper(head) == 0) {
                    return head;
                }
                //need addtional node
                ListNode newHead = new ListNode(1);
                newHead.next = head;
                return newHead;
            }
            
            // plus one for the rest of the list starting from node and return carry
         //because last node.next is null, let null return 1 and it is equivalent to  "plus one" to the least significant digit
       
            private int plusOneHelper(ListNode node) {
                if (node == null) {
                    return 1;
                }
                int sum = node.val + plusOneHelper(node.next);
                node.val = sum % 10;
                return sum / 10;
            }
        }

  • 0
    C

    @xuyirui Pretty clear and concise code. Even optimal solution is linear time const space.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.