Remove Duplicates from a Linked List

LinkedList의 head로부터 스캔해 가, 중복하는 노드가 있으면 삭제해, 중복이 없는 LinkedList의 head를 돌려줍니다.

설명

다음의 LinkedList가 주어집니다.

데이터가 중복되는 28과 14를 삭제하면 다음의 LinkedList가 됩니다.

Solution

Runtime Complexity O(n)

중복 여부를 정렬되지 않은 LinkedList를 스캔하므로 실행 시간은 O(n)입니다.

Space Complexity O(n)

중복되는지를 구분하기 위해서, HashSet의 데이터 구조를 사용해, 중복하는 데이터가 없는 경우는 최악 O(n)가 됩니다.

구현

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;
  }
}

생각

알고리즘은 간단하고 두 개의 포인터를 사용하면서 HashSet에 데이터를 넣습니다.
포인터, cur가 중복 데이터와 만나면, cur의 하나의 이전의 노드를 가리키는 포인터, prev를 사용해
prev.next = cur.next에서 중복 데이터를 포함하는 노드를 건너뜁니다.
메모리에 여유가 있는 경우는 이런 구현으로 문제 없다고 생각합니다.

그러나 메모리에 제한이 있으면 실행 시간을 희생해야합니다.
LinkedList의 순서를 변경할 수 있는 경우 O(n logn) 시간으로 정렬할 수 있습니다.
정렬 후 모든 중복 데이터를 포함하는 노드는 인접하므로 선형 스캔으로 삭제할 수 있습니다.

순서 변경이 허용되지 않는 경우
LinkedList의 각 노드에 대해 이전 노드에 동일한 데이터를 포함하는 노드가 있는지 스캔합니다.
이 알고리즘은 O(n^2)이며 여분의 공간이 필요하지 않지만 상당히 실행 시간을 희생합니다.