O(N) time & O(1) space Java solution with description


  • 1
    Z
    /**
     * Time complexity: In-order --> O(N)
     * Memory complexity: In-place --> O(1)
     * 
     */
    public ListNode deleteDuplicates(ListNode head) {
        
        //EDGE CASE
        if(head==null || head.next==null) return head;
        
        //INIT AUXILIARY NODES
        ListNode dummy = new ListNode(0);
        ListNode pre = dummy;
        ListNode prev = null;
        ListNode cur = head;
        
        //START REMOVAL
        while(cur!=null){
           //EDGE CASE1 -- START OF THE LINKED LIST
           if(prev==null){
               if(cur.val!=cur.next.val){
                   pre.next = cur;
                   pre = pre.next;
               }
               prev = cur;
               cur = cur.next;
               continue;
           }
           
           //BETWEEN START AND END
           if(cur.next!=null){
               if(cur.val != cur.next.val && cur.val!=prev.val){
                   pre.next = cur;
                   pre = pre.next;
               }
           }else{ //EDGE CASE2 --> END OF THE LINKED LIST
               if(cur.val!=prev.val){
                   pre.next = cur;
                   pre = pre.next;
               }
           }
           prev = cur;
           cur = cur.next;
        }
        
        //IMPORTANT TO DO THIS
        pre.next = null;
        
        //RETURN HEAD AFTER DELETION
        return dummy.next;
    }

Log in to reply
 

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