How can i improve my code??


  • 0
    D

    I m using an array to store the number of occurrences of each element,i have taken assumption dat elements are less than 100 and greater than -100

        int A[200]={0};
        ListNode *temp=head,*prev=head;
        while(temp)
        {
            if(temp->val<0)
            A[temp->val+200]++;//if element is negative then add size of array to it 
            else              //so that index always remain positive
            A[temp->val]++;
            temp=temp->next;
        }
        temp=head;
        while(temp)
        {
            if((temp->val<0 && A[temp->val+200]>1)||(temp->val>=0&&A[temp->val]>1))
            {
                if(temp==head)
                {               //if head is deleted than change head
                    head=temp->next;
                    prev=head;
                    free(temp);
                    temp=head;
                }
                else
                {               //otherwise just delete temp 
                    prev->next=temp->next;
                    free(temp);
                    temp=prev->next;
                }
            }
            else
            {
            prev=temp;
            temp=temp->next;
            }
        }
        return head;
    

    it takes O(n) for both running time n space.
    any advice in improving it??


  • 0
    A
    This post is deleted!

  • 1
    M

    There is no need to keep track of all distinct elements in the list. My code is in python. It only runs through the list once and needs constant space.

    {

        result=None
        p0=head
        p1=head
    
        if (head.val !=(head.next).val):
            result=head
    
        while(p0.next!=None):
            # the last two nodes
            if (p0.next.next==None):
                if (p0.val == p0.next.val):
                    if (p0!=p1):
                        p1.next =None
                else:
                    p1.next = p0.next
                    p1 = p1.next
                    # if result not initialized
                    if (result==None):
                        result =p1
                    
                    
            # in the middle                
            elif (p0.val < p0.next.val):
                if (p0.next.val<p0.next.next.val):
                    p1.next = p0.next
                    p1 = p1.next
                    # if result not initialized
                    if(result==None):
                        result = p1
        
            p0=p0.next
    
        return result
    

    }


  • 0
    D

    yes u r correct
    i actually didnt considered dat list is sorted


  • 3
    A

    Use a duplicate count and move into the final list.

    public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        
        if (null == head || null == head.next)
            return head;
        
        ListNode ptr = head;
        head = null;
        ListNode prev = null;
        int dupCount = 0;
        while (null != ptr)
        {
            // current matches the next, increase count and move to next
            if (null != ptr.next && ptr.val == ptr.next.val)
                dupCount++;
            else
            {
                // no dup found, need to move into final list
                if (0 == dupCount)
                {
                    // first time, set up new head
                    if (null == prev)
                        head = prev = ptr;
                    else
                    {
                        prev.next = ptr;
                        prev = ptr;
                    }
                }
                // onto next different node, reset dupCount
                dupCount = 0;
            }
            ptr = ptr.next;
        }
        
        // terminate the rest of the list if any
        if (null != prev)
            prev.next = null;
    
        return head;
    }
    

    }


  • 1
    P

    Here is my accepted code in python, O(n) with constant space complexity:

    class Solution:
        # @param head, a ListNode
        # @return a ListNode
        def deleteDuplicates(self, head):
            
            if head is None:
                return None
            
            head2 = None  # the first element of the new list 
            cur2 = None  # keep track of the latest element of the new list
    
            pre = head
            cur = head.next
            wrong_value = None # record the duplicate value
    
            while cur is not None:
                if cur.val>pre.val: # check if the previous value should be added
                    if pre.val!=wrong_value:
                            if head2 is None: 
                                    head2 = ListNode(pre.val)
                                    cur2 = head2
                            else:
                                    cur2.next = ListNode(pre.val)
                                    cur2 = cur2.next
                else:
                    wrong_value = cur.val
    
                pre = cur
                cur = cur.next
    
            if pre.val!=wrong_value: # we haven't checked the last one element of origin list
                if cur2 is not None: 
                    cur2.next = ListNode(pre.val)
                else: # head2 is Null if all the previous elements are duplicate
                    head2 = ListNode(pre.val)
                    
            return head2
    

    Basically, we record the duplicate value when the value of current node is same with the previous one. When we proceed to a new value, we check if the previous value is fine to be added to the new list. I think it's a rather straight-forward solution to me.


  • 0
    T

    here is my java solution,O(n) and constant space:

    public ListNode deleteDuplicates(ListNode head) {
    	if(head == null) 
    		return head;
    	ListNode root = new ListNode(0);
    	root.next = head;
    	ListNode lastValidate = root,pre = head;
    	head = head.next;
    	while(head != null){
    		if(head.val == pre.val){
    			while(head != null && head.val == pre.val){
    				head = head.next;
    			}
    			lastValidate.next = head;
    			if(head != null){
    			    pre = head;
    			    head = head.next;
    			}
    		}else{
    			lastValidate = pre;
    			pre = head;
    			head = head.next;
    		}
    	}
    	return root.next;
    }

  • 0
    O
    This post is deleted!

  • 0
    S

    Thanks for your post. However it would be better to post as answer with more detail content, including your thoughts and code comments. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


  • 0
    D

    Here's my answer. I think the basic idea is the same.........Draw graph. Use prev, cur and end to traverse the list, and use a flag dup to record whether there are dup nodes.......

    /**

    • Definition for singly-linked list.

    • struct ListNode {

    • int val;
      
    • ListNode *next;
      
    • ListNode(int x) : val(x), next(NULL) {}
      
    • };
      */
      class Solution {
      public:
      ListNode *deleteDuplicates(ListNode *head) {
      if(head==NULL) return head;
      ListNode *dummy = new ListNode(0);

       dummy->next = head;
       ListNode *prev=dummy;
      
       int dup = 0;
       for(ListNode *cur = head, *end=cur->next; cur!=NULL,end!=NULL; ){
           if (cur->val == end->val){
               end = end->next;
               dup=1;
               continue;
           }
           if(dup){
           prev->next=end;
           cur = end;
           end=cur->next;
           dup=0;
           }
           else{
               prev = cur;
               end = end->next;
               cur = cur->next;
           }
           
       }
       
       if (dup){
           prev->next = NULL;
       }
       
       return dummy->next;
      
    }
    

    };


  • 0
    D

    Here's my answer. I think the basic idea is the same.........Draw graph. Use prev, cur and end to traverse the list, and use a flag dup to record whether there are dup nodes.......

    /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ 
    
    class Solution { public: ListNode *deleteDuplicates(ListNode *head) { if(head==NULL) return head; ListNode *dummy = new ListNode(0);
    
        dummy->next = head;
        ListNode *prev=dummy;
    
        int dup = 0;
        for(ListNode *cur = head, *end=cur->next; cur!=NULL,end!=NULL; ){
            if (cur->val == end->val){
                end = end->next;
                dup=1;
                continue;
            }
            if(dup){
            prev->next=end;
            cur = end;
            end=cur->next;
            dup=0;
            }
            else{
                prev = cur;
                end = end->next;
                cur = cur->next;
            }
    
        }
    
        if (dup){
            prev->next = NULL;
        }
    
        return dummy->next;
    
    
    
    }
    
    };
    

  • 11
    S

    Here is my answer, When decide whether add the node to the result list or not, i use another point to find the lenght of sublist which has the same val.if the length is 1,then add the node to result list.

    public ListNode deleteDuplicates(ListNode head) {
        ListNode fakeHead = new ListNode(0);
        ListNode cur = fakeHead;
        ListNode suc = null;
        while(head!=null){
        	for(suc = head.next;suc!=null&&suc.val==head.val;suc = suc.next);
        	if(head.next==null||head.next==suc){
        		cur.next = head;
        		cur = cur.next;
        		cur.next = null;
        	}
        	head = suc;
        }
    
        return fakeHead.next;
    }

  • 0
    W

    Shall we concern about memory leaks problem? You just ignore the duplicate members.


  • 0
    S

    Using java,the gc will recycle the unused memory using gc algorithm.


  • -2
    V

    O(n) solution using simple linked list traversal and it takes constant space, Space Complexity O(1) Time Complexity O(n).

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

  • 0
    X

    maybe you put the ans in the wrong place


  • -1
    L

    Here is my answer. Instead of using a duplicate count, I'm using a boolean to determine whether a number is repeated.

    public class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if (head == null) return null;
        
        boolean rep = false;
        ListNode cur = new ListNode(0);
        cur.next = head;
        ListNode ficHead = cur;
        while (cur.next != null && cur.next.next!= null) {
            if (cur.next.val == cur.next.next.val) {
                cur.next = cur.next.next;
                rep = true;
            } 
            else 
            {
                if (rep) {
                    cur.next = cur.next.next;
                    rep = false;
                } else {
                    cur= cur.next; 
                }
            }
        }
        if (rep) cur.next = cur.next.next;
        return ficHead.next;
    }
    

    }


  • 0
    C

    since list is sorted, compare adjacent nodes seems enough...

    class Solution {
    public:
        ListNode *deleteDuplicates(ListNode *head) {
            for(ListNode *p = 0, *q = head; q; ){
                ListNode *r = q;
                while(r->next && r->next->val == q->val){
                    r = r->next;
                }
                if(q == r){ // q is distinct
                    p = q;
                }
                else{ // q ~ r are duplicates
                    (p ? p->next : head) = r->next;
                }
                q = r->next;
            }
            return head;
        }
    };

  • 0
    S

    I think we should!


  • 0

    Here's my code. The idea is to use two pointers. One points to the latest stable (or final) result, the other points to the node we're going to compare in next iteration.

    Here's the C# code

    public ListNode DeleteDuplicates(ListNode head) {
    
        if (head == null || head.next == null) {
            return head;
        }
    
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
    
        ListNode stableNode= dummyHead;            
        int value = stableNode.next.val;
        ListNode current = stableNode.next.next;
    
        while(current != null) {
            // same value as previous one. remove all nodes.
            if (current.val == value) {
                stableNode.next = null;
            }
            else { // we see a different node.
                if (stableNode.next != null) { // in this case, stableNode.next is stable result, move one step
                    stableNode = stableNode.next;
                }
    
                stableNode.next = current;
                value = current.val;
            }
    
            current = current.next;
        }
    
        return dummyHead.next;
    }
    

Log in to reply
 

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