Удаление дубликатов из связанного списка в Java без использования дополнительного буфера

Question

Я рассматриваю некоторые фрагменты кода для предстоящего теста. Я видел это в своих заметках и только сейчас понял, что этот код для метода 1 на самом деле не удаляет дубликаты, если список таким образом A -> B -> C -> A. Я написал альтернативную функцию (метод 2) что я думаю, что на самом деле будет работать. Что, вы парни, думаете? Метод 1 на самом деле не работает, и я отслеживаю это неправильно? PS В настоящее время мы не допускаем компиляторы:)

Вот код и краткое введение того, что он должен делать.

МЕТОД 1: То, что я думаю, не работает, когда есть две точные вещи в голове и хвосте. Напишите код для удаления дубликатов из несортированного списка БЕЗ буфера. Wwe может выполнять итерацию с двумя указателями: "current" выполняет обычную итерацию, в то время как "runner" выполняет итерацию по всем предыдущим узлам для проверки на наличие ошибок. Бегун увидит только один дубликат на узел, потому что, если бы было несколько дубликатов, они были бы уже удалены.

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

Я думал, что это сработает. МЕТОД 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

Лучший способ - отсортировать связанный список. затем повторите и проверьте, совпадают ли смежные элементы. Если да, удалите соседний элемент. Это метод O(nlogn) без использования дополнительного буфера.

Answer 2

Я не уверен, что для вас означает "без дополнительного буфера", но так как я ленивый человек и, как мне кажется, другие люди гораздо лучше пишут алгоритмы, чем я, я бы поместил весь связанный список в HashSet и обратно в связанный список. Это позволит легко удалить дубликаты:

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

Или, если вы хотите сохранить порядок элементов

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

Теперь, так как это домашнее задание, и вы, похоже, сами реализуете LinkedList, вполне возможно, что это решение нежизнеспособно;-) Но в любом случае оно будет иметь сложность O(n), а не O(n). ^2) как ваши методы 1 и 2, которые уже могут быть намного лучше для вас...?

Answer 3

Я добавил свой код здесь, но меня смущает сложность времени: O(n) или O(nlogn)? Дайте мне знать об этом.

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

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

Это использует метод двойного указателя. Без использования дополнительного пространства мы можем иметь две точки указателя cur(Slow) и next(Fast). Для каждого указателя cur проверяются данные в следующем указателе. Если совпадение найдено, указатели корректируются так, чтобы указывать на следующий соответствующий узел. Надеюсь это поможет.

Answer 5

Модификация, сделанная в функции выше, чтобы исправить логику Но я не уверен, какова временная сложность функции. Это O(n^2) или O(n)

открытый статический узел removeDuplicatesFromUnsortedLinkedListWithoutExtraSpace(голова узла){ 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;
}