c - 並べ替えられたリンク リストから重複する要素を削除する

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

コードは次の要素を調べるため、次のように、1 つ前の要素に到達したら停止する必要があります。

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

条件の最初の部分を持つ唯一の理由は、空のリストをトラップすることです。

さらに、要素を削除するときにポインタを進めるべきではありません。そうしないと、3 つ以上の要素の実行を正しく処理できません。

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

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 4

私によると、現在のノードが最後のノードではないことを最後に確認する必要があります。適切な説明とコードは次のとおりです 。 http://www.dscoding.com/2016/11/remove-duplicates-from-sorted-linked.html

Answer 5

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