Algorithm gymnastics 11

Remove Duplicates from a Linked List It scans from the head of the LinkedList, deletes any duplicate nodes, and returns the head of the LinkedList with no duplicates.

Description

Given the following Linked List: If you delete 28 and 14 with duplicate data, you will get the following Linked List. Solution Runtime Complexity O(n) The execution time is O (n) because it scans the unsorted Linked List for duplicates. Space Complexity O(n) Use the HashSet data structure to distinguish between duplicates, and if there are no duplicates, the worst is O (n).

Implementation

removeDuplicate.java

class removeDuplicate{
  public LinkedListNode remove_duplicates(LinkedListNode head) 
  {
    if (head == null || head.next == null) {
      return head;
    }

    LinkedListNode cur = head;
    LinkedListNode prev = head;

    HashSet set = new HashSet();

    while (cur != null) {
      if (!set.contains(cur.data)) {
        set.add(cur.data);
        prev = cur;
      } else {
        prev.next = cur.next;
      }
      cur = cur.next;
    }
    return head;
  }
}

Thoughts

The algorithm is simple, using two pointers to populate the HashSet. If the pointer and cur encounter duplicate data, use the pointer and prev that point to the node immediately before cur. skip nodes containing duplicate data with prev.next = cur.next. If there is enough memory, I think that there is no problem with such an implementation.

However, if you have limited memory, you have to sacrifice execution time. If you are allowed to reorder the LinkedList, you can sort by O (n logn) time. After sorting, the nodes containing all the duplicate data are adjacent and can be removed by a linear scan.

If reordering is not allowed For each node in the LinkedList, you will be scanning for nodes in the previous node that contain the same data. This algorithm is O (n ^ 2) and does not require extra space, but at the expense of significant execution time.