Удалите повторяющиеся элементы из отсортированного связанного списка

Question

Я пытаюсь выполнить программу C для удаления дубликатов из сортированного связанного списка, и я использую простую концепцию прохождения списка из начального узла. При перемещении сравните каждый узел со следующим узлом. Если данные следующего узла совпадают с текущим узлом, я удаляю следующий узел.

Мой код:

struct node *remove_dup(struct node *start) 
{ 
    struct node *p,*tmp; 
    p=start; 
    while(p!=NULL) 
    { 
     if(p->info==p->link->info) 
     { 
      tmp=p->link; 
      p->link=p->link->link; 
      free(tmp); 
     } 
     p=p->link; 
    } 
    return start; 
} 

Это не дает мне правильный ответ! Что случилось с моим исполнением? Является ли моя концепция неправильной?

Answer 1

Поскольку ваш код проверяет следующий элемент, вам нужно остановиться, когда вы находитесь на элементе позапрошлого, как это:

while (p != NULL && p->link != NULL) { 
    ... 
} 

Единственная причина, чтобы иметь первую часть условия является ловушкой пустые списки.

Кроме того, вы не должны продвигать указатель при удалении элемента. В противном случае вы не будете обрабатывать пробеги из более чем двух элементов правильно.

Answer 2

struct node *remove_dup(struct node *start) 
{ 
    struct node *p,*next; 

    for(p=start; p; p = next) { 
     next = p->link; 
     if(!next || p->info != next->info) continue; 
     p->link = next->link; 
     free(next); 
     next = p; 
    } 
    return start; 
} 

Или эквивалент (без баловаться с рядом)

struct node *remove_dup(struct node *start) 
{ 
    struct node *p; 

    for(p=start; p;) { 
     struct node *next = p->link; 
     if(!next || p->info != next->info) { p = next; continue; } 
     p->link = next->link; 
     free(next); 
    } 
    return start; 
} 

Answer 3

Мой ответ в Java:

public void removeDuplicate() { 
    if (first == null) { 
     throw new NoSuchElementException("The linkedlist contains no nodes."); 
    } 
    Node temp = first; 
    while (temp != null && temp.next != null) { 
     if (temp.element == temp.next.element) { 
      temp.next = temp.next.next; 
     } else { 
      temp = temp.next; 
     } 
    } 
} 

Answer 4

void removeDuplicate() 
{ 
    if(head == NULL) 
     return; 
    Node<T>* pPre = head; 
    Node<T>* pCur = pPre->pNext; 
    while (pCur != NULL) 
    { 
     if(pCur->elemet == pPre->elemet) 
     { 
      pPre->pNext = pCur->pNext; 
      pCur = pPre->pNext; 
     } 
     else 
     { 
      pPre = pCur; 
      pCur = pPre->pNext; 
     } 
    } 

} 

Мой ответ на C++.

Answer 5

Я имел дело с одной и той же проблемой в java и придумал очень маленькое решение после того, как попытался изначально. Взгляни, пожалуйста.

Node RemoveDuplicates(Node head) { 
    Node curr = head; 
    if(head==null) 
     return head; 
    while(curr.next!=null){ 
     if(curr.data == curr.next.data) 
      curr.next = curr.next.next; 
     else curr = curr.next; 
    } 
    return head; 
} 

Answer 6

По моему мнению, в конце нужно также проверить, что ваш текущий узел не является последним узлом. Вот правильное объяснение и приведенный код: http://www.dscoding.com/2016/11/remove-duplicates-from-sorted-linked.html