One iteration O(n) recursion


  • 0
    H

    We need to know whether the adding to the rest of the numbers will cause a carry action. So take care of this and pass to next recursion.

        public ListNode plusOne(ListNode head) {
            if(head == null) return null;
            boolean c = carry(head);
            if(c){ 
                ListNode root = new ListNode(0);
                root.next = head.next;
                head.val = 1;
                head.next = root;
            }
            return head;
        }
        
        public boolean carry(ListNode head){
            if(head.next == null){
                head.val = (head.val +1) % 10;
                return head.val == 0;
            }
            else if(carry(head.next)){
                if(head.val == 9){
                    head.val = 0;
                    return true;
                }else{
                    head.val++;
                    return false;
                }
            }
            
            return false;
        }

Log in to reply
 

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