Accepted Java solution with 2*O(n)


  • 0
    A
    1. Using every node's value as map's key and value.So duplicated numbers in list can only appear once in map
    
    2. Using every node's value as flag's key, and 1 or 0 as value. 1 for duplicated ,0 for not duplicated
    
    3. I get the min number and max number in given list
    
    4. Return the list which contains all none-duplicated nodes
    
    
    
     class Solution{
                public ListNode deleteDuplicates(ListNode head) {
                    HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
                    HashMap<Integer,Integer> flag=new HashMap<Integer,Integer>();
                    if(head==null) return head;
                    int min=head.val;
                    int index=0;
                    int max=0;
                    while(head!=null)
                    {
                        if(map.containsValue(head.val))    flag.put(head.val,1);
                        else flag.put(head.val,0);
                        map.put(head.val,head.val);
                        if(head.next==null) max=head.val;
                        head=head.next;
                        index++;
                    }
                    ListNode result=new ListNode(0);
                    ListNode first=result;
                    for(int i=min;i<=max;i++)
                    {
                        if(map.get(i)!=null)
                        {
                            if(flag.get(i)!=1)
                            {
                                result.next=new ListNode(map.get(i));
                                result=result.next;
                            }
                        }
                    }
                return first.next;
            }
        }

Log in to reply
 

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