3 Line JAVA recursive solution


  • 137
    W

    This solution is inspired by renzid https://leetcode.com/discuss/33043/3-line-recursive-solution

    public ListNode deleteDuplicates(ListNode head) {
            if(head == null || head.next == null)return head;
            head.next = deleteDuplicates(head.next);
            return head.val == head.next.val ? head.next : head;
    }
    

    Enjoy!


  • 1
    X

    Really admirable solution and need deep understanding of recursion~


  • 0
    H

    Good job! Short, effective. You must be a very good programmer.


  • 0
    S

    This solution is cool, dude


  • 21
    L

    I highly doubt if we should use recursion in solving linked list problems. We use it for tree because its stack space is O(logn), where n is the number of nodes. But it's O(n) space required for linked list, which is very likely to be stack overflow. Point me out if you hold a different opinion.


  • 0
    S

    that's really cool, man!


  • 0
    W

    helpful,thanks


  • 2

    The base case can be made simpler

        public ListNode deleteDuplicates(ListNode head) {
            if (head == null) return head;
            head.next = deleteDuplicates(head.next);
            return head.next != null && head.val == head.next.val ? head.next : head;
        }
    

  • 0
    J

    My 3 lines C++ iterative code. Just for fun-^
    Although 2 for loops are used, the time complexity remains O(n).

    public:
        ListNode* deleteDuplicates(ListNode* head) {
            for(ListNode *p1 = head, *p2=NULL; p1 != NULL; p1 = p1->next = p2){
                for(p2 = p1->next; p2 != NULL && p2->val == p1->val; p2 = p2->next){}}
            return head;
        }
    };

  • 0
    B

    Outstanding!


  • 0
    W

    That‘s awesome


  • 0
    P

    @wen587sort said in 3 Line JAVA recursive solution:

    This solution is inspired by renzid https://leetcode.com/discuss/33043/3-line-recursive-solution

    public ListNode deleteDuplicates(ListNode head) {
            if(head == null || head.next == null)return head;
            head.next = deleteDuplicates(head.next);
            return head.val == head.next.val ? head.next : head;
    }
    

    Enjoy!

    Admirable solution!!


  • 0
    M

    @wen587sort It is beautiful ! :-D


  • 0
    A

    @lisen I have the same question. But I don't understand what do you mean stack overflow in this case?


  • 0
    E

    @akailotusxi What they mean is that every time we make a recursive call, it places a frame on our stack memory. Because we much make a recursive call for each node in list, recursion is often not the best way to manipulate lists if it can be avoided.


  • 0
    A

    @ElayMarco
    I see, thanks for your reply.
    Since that recursive might cause stack overflow, why do people like to use recursive a lot? There are many concise codes that are written in recursive.
    Does recursive used a lot in the real industry? Sorry, I have no much working experience.


  • 0
    E

    @akailotusxi Well, on sites like these one's, I believe a lot of times people want to post 'other ways' of doing things, which is good. Recursive solutions sometimes require less coding to implement, and as a by-product of this look more clever or elegant. Recursion is just a tool. Sometimes the job calls for a hammer. Other times, a hammer is not suitable. Part of being a good programmer is knowing when to use which tools. But on sites like these, some people like to 'sharpen their tools' by writing recursive solutions to problems where iterative solutions are more efficient. Think of it as practice.


  • 0
    A

    @ElayMarco
    I see. We need to choose the right tool for each question instead of using recursive all the time. Thank you, Marco. Your information is very useful.


  • 1
    F

    Well, I don't think it's a proper use of recursion anyway.
    Your algorithm remind me of a book named <<Data Structures and Algorithm Analythis in C++ 3rd>> . In chapter 3, it gives us an a bad use of recursion:

    template<typename Iterator>
    void Print(Iterator start, Iterator end, ostream &out = cout)
    {
        if (start == end)
        {
            return;
        }
        out << *start++ << endl;
        Print(start, end, out);
    }
    

    And here is the comment beside

    Unfortunately, if the container contains 20000 elements to print, there will be a stack of 20,000 activation records ...
    So this program is likely to run out of stack space

    This is why I disagree with you.


Log in to reply
 

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