Java recursive solution


  • 27
    H

    At the first glance, I want to reverse the inputs, add one, then reverse back. But that is too intuitive and I don't think this is an expected solution. Then what kind of alg would adding one in reverse way for list?

    Recursion! With recursion, we can visit list in reverse way! So here is my recursive solution.

    public ListNode plusOne(ListNode head) {
        if( DFS(head) == 0){
            return head;
        }else{
            ListNode newHead = new ListNode(1);
            newHead.next = head;
            return newHead;
        }
    }
    
    public int DFS(ListNode head){
        if(head == null) return 1;
        
        int carry = DFS(head.next);
        
        if(carry == 0) return 0;
        
        int val = head.val + 1;
        head.val = val%10;
        return val/10;
    }

  • 6
    B

    same idea

    public ListNode plusOne(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        helper(dummy);
        return dummy.val == 0 ? head : dummy;
    }
    
    private int helper(ListNode node){
        if(node == null) return 1;
        node.val += helper(node.next);
        if(node.val <= 9) return 0;
        node.val %= 10;
        return 1;
    }

  • 0
    A

    Same idea, a little conciser. Btw in this new text editor I don't have the tool for making a code block? Am I missing anything?
    // code in C#

    public class Solution {
        public ListNode PlusOne(ListNode head) {
            if(head==null) { return new ListNode(1); }
            ListNode res = new ListNode(1);
            res.next = head;
            return plusOne(head)>0 ? res : head;
        }
        private int plusOne(ListNode head){
            int sum = head.val + (head.next==null ? 1 : plusOne(head.next));
            head.val = sum%10;
            return sum/10;
        }
    }

  • 0
    G

    @bbhs There's no need to use % operator. The last two line can be simply:

        node.val = 0;
        return 1;

  • 0

    very decent thinking process, very nice and clean sharing.
    "how to add value reversely?" it's DFS


  • 1
    D

    if the input head is a null pointer, your method would return [1] instead of []. I think you need change if(head == null) return 1 to if(head == null) return 0 and add one more base case if(!head -> next)


  • 0
    M

    Great solution to return int directly and I'm a little stupid with the Listnode solution.

    public class Solution {
        private int cnt = 1;
        public ListNode plusOne(ListNode head) {
            ListNode fake = helper(head);
            if (cnt == 1) {
                ListNode node = new ListNode(1);
                node.next = fake;
                return node;
            }
            return fake;
        }
        private ListNode helper(ListNode head) {
            if (head == null) return head;
            head.next = helper(head.next);
            int tmp = head.val;
            head.val = (tmp + cnt) % 10;
            cnt = (tmp + cnt) / 10;
            return head;
        }
    }
    

Log in to reply
 

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