Concise solution and memory freeing


  • 28
    A

    I noticed that the solutions posted here are too long and complicated. They use unnecessary variables and/or checks etc.
    The solution can be much more concise. Here is my solution:

    class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            ListNode* cur = head;
            while (cur) {
                while (cur->next && cur->val == cur->next->val)
                    cur->next = cur->next->next;
                cur = cur->next;
            }
            return head;
        }
    };
    

    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(...);.


  • 0
    V

    I think that instead of using two while cycles this can be solved using only one and recursion. With something like this:

    class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            if ( head == NULL ) return head;
            ListNode *list = head;
            while( list != NULL && list -> next != NULL )
            {
                if ( list -> val == list -> next -> val )
                {
                    list -> next = list -> next -> next;
                    deleteDuplicates( list );
                }
                list = list -> next;
            }
            return head;
        }
    };
    

  • 40
    T

    The is no need to use two while loop and also no need to use recursion

    public class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            if (head == null) return head;
            
            ListNode cur = head;
            while(cur.next != null) {
            	if (cur.val == cur.next.val) {
            		cur.next = cur.next.next;
            	}
            	else cur = cur.next;
            }
            return head;
        }
    }

  • -2
    V
    void remove_duplicated_nodes_no_storage(listnode* head)
        {
        listnode* curr = head;
        while(curr)
            {
            listnode* prev = curr;
            listnode* c = curr->next;
            
            while(c)
                {
                if(curr->data == c->data)
                    {
                    prev->next = c->next;
                    free(c); c = NULL;
                    c = prev->next;
                    }
                else
                    {
                    prev = c;
                    c = c->next;
                    }
                } //end while inner
                
            curr = curr->next;
            } //end while outer
        }
    

  • 3
    L

    One 'if' and one 'while', the simplest you can ever get:

    ListNode *deleteDuplicates(ListNode *head) {
        ListNode*cur=head,*tail=head;
        while(cur){
            if(cur->val!=tail->val){
                tail->next=cur;
                tail=cur;
            }
            cur=cur->next;
            tail->next=NULL;
        }
        return head;
    }

  • 0
    Z

    The only way to delete the not needed node in java that I know of is to null out the node to avoid loitering. What are the proper ways to do that in C++?


  • 0
    L

    nice solution, and shorter than mine. cool!.


  • 0
    P

    good solution! thank u!


  • 0
    A

    Two while loops doesn't really matter, it does not change the time complexity to O(n2) instead because it will still run 1 pass. Same with recursion, recursion might cost a little bit more on other craps though, but overall not too much difference.


  • 0
    L

    if so, some of the left nodes are also modified(the pointer to next node changes), can these nodes still be allocated in other ways?


  • 0
    Y

    I know it's a stupid question. But why return 'head'? There is no operation of 'head' during the process. I'm just beginning to learn programming. Thanks in advance.


  • 0
    H
    This post is deleted!

  • 0
    S

    @Yan_Sylvia_Liu Since the variable cur and head point to the same ListNode, any operation on cur will affect head. Because we changed cur along the way, we need to return head cause it is the real "root".


  • 0
    S

    I don't get where do you free the memory. Or you did not in this code?


Log in to reply
 

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