Removing duplicates from a linked-list in Java without the use of extra buffer

Question

I am reviewing some snippets of code for an upcoming test. I saw this in my notes, and just now realized that this code for method 1 doesn't actually remove duplicates if the list is in this way A -> B -> C -> A. I wrote an alternative function (method 2) that I think will actually work. What do you guys think? Does method 1 actually not work, and I'm tracing it wrong? p.s. We are not allowed compilers at this time :)

Here is the code, and a short introduction of what it should do.

METHOD 1: What I think doesn't work when there are 2 exact things at the head and tail. Write code to remove duplicates from an unsorted list WITHOUT a buffer. Wwe can iterate with two pointers: “current” does a normal iteration, while “runner” iterates through all prior nodes to check for dups. Runner will only see one dup per node, because if there were multiple duplicates they would have been removed already.

public static void deleteDuplicates1(LinkedListNode head) {
if (head == null) return;
LinkedListNode previous = head;
LinkedListNode current = previous.next;
while (current != null) {
    LinkedListNode runner = head;
       while (runner != current) { // Check for earlier dups
          if (runner.data == current.data) {
              LinkedListNode tmp = current.next; // remove current
              previous.next = tmp;
              current = tmp; // update current to next node
              break; // all other dups have already been removed
              }
              runner = runner.next;
          }
          if (runner == current) { // current not updated - update now
               previous = current;
               current = current.next;
              }
         }
 }

I was thinking this would work. METHOD 2:

    public void removeDuplicates2(){  
    Node current = null;  
    Node tracer = null;  

   for( current = head.next; current!=null; current=current.next){  
       for(tracer=head; tracer!=current; tracer=tracer.next){  
          if(tracer.data == current.data)  
          //DELETE THE NODE IN CURRENT  
       }  
    }  

}

Answer 1

The best way is sort the linked list. then iterate and check if adjacent elements are the same. If yes, delete the adjacent element. This is an O(nlogn) method without using an extra buffer.

Answer 2

I'm not sure what "without an extra buffer" means to you, but since I'm a lazy person and since I think other people are far better at writing out algorithms than me, I'd put the whole linked list into a HashSet and back to a linked list. That will remove duplicates easily:

LinkedList result = new LinkedList(new HashSet(inputList));

Or, if you want to preserve the order of elements

LinkedList result = new LinkedList(new LinkedHashSet(inputList));

Now since this is a homework question and you seem to be implementing a LinkedList yourself, it may well be that this solution is not viable ;-) But in any case, it will be of O(n) complexity, and not O(n^2) like both your methods 1 and 2, which might already be a lot better for you...?

Answer 3

I have added my code here but I am confused about the time complexity will it be O(n) or O(nlogn)? Let me know about this.

public Node removeDuplicatesFromUnsortedLinkedListWithoutExtraSpace(Node head)
{
    if(head == null || head.next == null)
        return head;

    Node prev = head;
    Node curr = head.next;
    Node temp = curr;

    while(prev.next!=null)
    {
        if(prev.data == curr.data)
        {
            temp.next = curr.next;
            curr = curr.next;
        }
        else
        {
            if(curr != null)
            {
                temp = curr;
                curr = curr.next;
            }

            if(curr == null)
            {
                prev = prev.next;
                curr = prev.next;
                temp = curr;
            }
        }
    }
    return head;
}

Answer 4

Modification made to the function above to rectify the logic But i am not sure what is the time complexity of the function. Is it O(n^2) or O(n)

public static Node removeDuplicatesFromUnsortedLinkedListWithoutExtraSpace(Node head){ if(head == null || head.next == null) return head;

    Node prev = head;
    Node curr = head.next;
    Node temp = prev;

    while(prev.next!=null){
        if(curr != null){
            if(prev.data == curr.data){
                temp.next = curr.next;
                curr = curr.next;
            }else {
                temp = curr;
                curr = curr.next;
            }
        }else{
            prev = prev.next;
            curr = prev.next;
            temp = prev;
        }
    }
    return head;
}

Answer 5

public static Node removeDuplicates(Node head) {
    Node cur = head;
    Node next = cur.next;
    while (cur != null && cur.next != null) {
        next = cur;
        while (next.next != null) {
            if (cur.data == next.next.data) {
                Node d = next.next;
                next.next = next.next.next;
            } else {
                next = next.next;
            }
        }
        cur = cur.next;
    }
    return head;
}

This uses the double pointer method. Without using any extra space, we can have two points cur(Slow) and next(Fast) pointers. For each cur pointer the data in the next pointer is checked. If a match is found then the pointers are adjusted to point to the next respective node. Hope this helps.