[JAVA] 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: Screen Shot 2020-01-04 at 12.00.09.png If you delete 28 and 14 with duplicate data, you will get the following Linked List. Screen Shot 2020-01-04 at 12.00.23.png 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.

Recommended Posts

Algorithm gymnastics 12
Algorithm gymnastics 10
Algorithm gymnastics 3
Algorithm gymnastics 9
Algorithm gymnastics 14
Algorithm gymnastics 2
Algorithm gymnastics 7
Algorithm gymnastics 8
Algorithm Gymnastics 17
Algorithm Gymnastics 18
Algorithm gymnastics 11
Algorithm gymnastics 5
Algorithm gymnastics 4
Algorithm Gymnastics 24 Subsets
Algorithm Gymnastics 23 Merge Intervals
Algorithm Gymnastics 21 LinkedList Cycle
Algorithm Gymnastics 24 Cyclic Sort
Algorithm Gymnastics 19 No-repeat Substring
Algorithm exercise 6
Algorithm Gymnastics 24 Reverse a Linked List
Algorithm exercises 13
Algorithm Gymnastics 20 Pair with Target Sum
Algorithm Gymnastics 22 Squaring a Sorted Array
Algorithm Gymnastics 24 Middle of the Linked List
Python memorandum (algorithm)
Dictionary learning algorithm
String search algorithm