2 solutions, using stack and recursion


  • 0
    T
    public ListNode plusOne(ListNode head){
            if (null == head){
                return  null;
            }
    
            int carry = helper(head);
            if (carry > 0){
                ListNode n = new ListNode(carry);
                n.next = head;
                head = n;
            }
    
            return head;
        }
    
        public int helper(ListNode head){
            if (null == head){
               // last , null node returns a 1 as a carry
                return 1;
            }
    
            int carry = helper(head.next);
            int nodeVal = head.val;
            int total = nodeVal + carry;
    
            carry = total / 10;
            int newNodeVal = total % 10;
            head.val = newNodeVal;
            return carry;
        }
    

    This solution uses stack.

        public ListNode plusOne(ListNode head){
            if (null ==head){
                return null;
            }
    
            Stack<ListNode> stack = new Stack<>();
            ListNode cur = head;
    
            while(null != cur){
                stack.push(cur);
                cur = cur.next;
            }
    
            int carry  = 0;
            ListNode peek = stack.peek();
            peek.val= peek.val + 1;
    
            ListNode newHead = null;
    
            while (!stack.isEmpty()){
                int val = stack.pop().val;
                int sum = val + carry;
                carry = sum / 10;
                int i = sum % 10;
                ListNode n = new ListNode(i);
    
                n.next = newHead;
                newHead = n;
            }
    
            if (carry > 0 ){
                ListNode n = new ListNode(carry);
    
                n.next = newHead;
                newHead = n;
            }
    
            return newHead;
        }
    

Log in to reply
 

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