Java O(n) solution with explanation


  • 0
    M

    Idea:
    Use a dummy head node point the head. Define 3 pointers: pre, cur, post. Detect the post node whether its value is equal to the current node. If true delete ALL duplicate nodes. And then delete the current one.

    public ListNode deleteDuplicates(ListNode head) {
            if(head==null || head.next==null) return head;
            ListNode dummy = new ListNode(head.val+1);
            dummy.next = head;
            ListNode pre = dummy, cur = head, post = head.next;
            while(post != null){
                if(cur.val == post.val){
                    while(post!=null && cur.val == post.val){ 
                        cur.next = post.next;
                        post = post.next;
                    }
                    pre.next = post;
                    cur = post;
                    if(post!=null) post = post.next;
                } else {
                    pre = pre.next;
                    cur = cur.next;
                    post = post.next;
                }
            }
            return dummy.next;
        }
    

Log in to reply
 

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