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

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

2 голосов
/ 02 января 2011

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

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

МЕТОД 1: Что я думаю, что не работает, когда есть2 точные вещи в голову и хвост.Напишите код для удаления дубликатов из несортированного списка БЕЗ буфера.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  
       }  
    }  

}

Ответы [ 5 ]

8 голосов
/ 02 января 2011

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

6 голосов
/ 02 января 2011

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

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

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

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

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

2 голосов
/ 15 февраля 2014

Я добавил свой код здесь, но меня смущает сложность времени: 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;
}
0 голосов
/ 14 марта 2017 
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 проверяются данные в следующем указателе. Если совпадение найдено, указатели корректируются так, чтобы указывать на следующий соответствующий узел. Надеюсь это поможет.

0 голосов
/ 11 августа 2014

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

общедоступный статический узел1004 *

...