Simple and clear c++ recursive solution


  • 37
    L
    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            if (!head) return 0;
            if (!head->next) return head;
            
            int val = head->val;
            ListNode* p = head->next;
            
            if (p->val != val) {
                head->next = deleteDuplicates(p);
                return head;
            } else {
                while (p && p->val == val) p = p->next;
                return deleteDuplicates(p);
            }
        }
    };

  • 0
    S

    This is what I want!


  • 0
    L
    This post is deleted!

  • 0
    L

    Haven't thought of a recursive solution. Cool !


  • 0
    W

    Very Cool !!


  • 9
    V

    Ideally, you should free the memory. This solution has memory leaks.


  • 0
    P

    @vishal51
    I read some information as follows:
    Note about freeing memory. We need to free memory when we delete a node. But don't use delete node; construct on an interview without discussing it with the interviewer. A list node can be allocated in many different ways and we can use delete node; only if we are sure that the nodes were allocated with new TreeNode(...);.

    Does it mean leaving unreleased nodes there is okay?


  • 0
    A

    lots of memory leakage.


  • 0
    W

    @lge Similar idea, different implementation : )

    ListNode* deleteDuplicates(ListNode* head) {
            if(!head || !head->next) return head;
            auto run = head->next;
            while(run && run->val == head->val) run = run->next;
            if(run != head->next) return deleteDuplicates(run);
            head->next = deleteDuplicates(run);
            return head;
        }
    

  • 0
    X

    @wangxinbo same idea haha

    class Solution {
    public:
        ListNode* deleteDuplicates(ListNode* head) {
            if(head == nullptr || head->next == nullptr) return head; //edge case
    		
    		ListNode* p = head;
    		while(p->next && p->next->val == p->val){
    		    p = p->next;
    		}
    		
    		head->next = deleteDuplicates(p->next); 
    		return (p!=head)? head->next : head;
        }
    };
    

  • 0
    N

    This helped a lot!! Thanks :D


Log in to reply
 

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