ノードへのポインタのみが与えられている場合、単一のリンクされたリストからノードを削除する

Question

これはインタビューで私に提起された質問です。

"ノードを削除する必要があります。そのノードを削除する関数を作成する必要があります。削除するノードのアドレスのみを入力として受け取ります

次のような回答をしました。次のノードの内容を削除するノードにコピーし、次のノードを削除します。

Deleting a middle node from a single linked list when pointer to the previous node is not available

しかし、インタビュアーが再び私に尋ねた、私が最後のノードのアドレスを渡す場合。私は彼に言った、次はNULLになるので、そのNULLを次のノードへのアドレスと共にデータフィールドにコピーする。これもNULLである。それから彼は私にちょっと理解していないポインタがついているという問題があると私に言った。いくつかの人がこの問題に光を投げてくれますか？これには一般的な解決策がありますか？

更新（2日後）：もう少し追加します。リストの最後に特別なノードがないことを考慮してください。最後のノードはNULLを指し、そのノードが入力として与えられている場合、最後のノードの前にNULLを指すようにする方法。それとも不可能なのでしょうか？

簡単に言えば：ノードは、関数への入力として与えられた場合、それを参照するポインタを作成する方法、ポイントコピーする次のノードを指している他の要素が存在する場合

Answer 1

ダングリングポインタ：コンピュータプログラミングにおける

（http://en.wikipedia.org/wiki/Dangling_reference）

ダングリングポインタと野生のポインタが有効なを指していない ポインタです適切な型のオブジェクト。 これらはメモリ安全違反の特別なケースです。

オブジェクトが削除または割り当て解除されたときダングリングポインターが発生します。 ポインタの値を変更しないで、ポインタ は割り当て解除されたメモリのメモリ位置を指します。 は、以前に解放されたメモリを別のプロセスに再割り当てする可能性があるため、 元のプログラムが（今）ダングリングポインタを参照解除すると、メモリに のデータが完全に異なる可能性があるため、予測できない動作が発生することがあります。あなたの答えで

、あなたが実際にポインタが参照されている可能性があります次ノードを削除指定されたノードを削除します。それはどのように絡み合ってポインタの問題が発生するかです。

（1）メモを明確にすると、リストの外部参照はありません。 （2）インタビュアーが指摘したように、ポインタの絡みが発生する可能性があります。

（1）と（2）の両方を同時に正しくすることはできません。つまり、どこかに誤解があります。最後のノードを削除について

：

しかし、インタビュアーが再び私に尋ねた、私は 最後のノードのアドレスを渡す場合。私は彼に言った、次はNULLになるので、NULL を、次のノードへのアドレスとともにデータフィールドにコピーします。これは でもNULLです。

（1）NULLを指すポインタp、（2）データフィールドにNULLを持つリンクされたリストノード、の2つが混乱していると思います。

データ構造がa -> b -> c -> dであるとします。 NULLをdsデータフィールドに書き込んでも、そのフィールドにNULLポインタがあると魔法のようにはなりません。next

最後のノードを削除することができます。リンクされたリストには、決して削除されない特別な最後のノードが存在します。たとえば、a -> b -> c -> d -> LASTここで、LASTは実際に最後の要素であることを示すデータフィールドに特殊な値を持ちます。ここでdを削除するには、LASTを削除してdのデータフィールドに特別な値を書き込んでください。

これはまさにあなたがインタビュー中に伝えようとしたものです。その場合、あなたとインタビュアーとの間に何らかのミスコミュニケーションがあったに違いありません。

Answer 2

をNULLに現在のノードに移動して削除すると、この操作でバグが発生します。あなたの答えでは、リストへの外部参照がない場合にのみあなたのソリューションが機能することを強調しておきます。

データ構造に特定の「最後のノード」要素が追加されている場合にのみ、ソリューションは最後のノードで動作します。 （スモールトークを使用している場合は、self become: nilと書くことができます）他の言語に類似するものはありません。

いいえ、リストへの外部参照がある場合は一般的な解決法はありません。インタビュアーは、あなたが本当に知識があるのか​​、それとも暗記された答えを繰り返しているのかを見たいと思っています。

Answer 3

ステップ：ノード間（I + 1）（I）から

1. コピーデータ
2. コピー一時変数に、第2ノード（I + 1）のNEXT。
3. 今すぐ2番目のノード（i + 1）を削除します。//前のノードへのポインタは必要ありません。

機能：

void delete_node(node* node) 
{ 
    node->Data = node->Next->Data; 
    node* temp = node->Next->Next; 
    delete(node->Next); 
    node->Next = temp; 
} 

Answer 4

おそらくあなたのリンクリストトラバースがnullを指すいずれかのノードが値に関係なくnullノードであることを前提とする必要があるかもしれません...

a->b->c->d->NULL 

のでdnullノードであり、ノードはノードと見なすべきではありません。特殊な値を使うのは、一般的な意味では正しくないので、この方法で節約することができます。それ以外の方法では、以前のノードがnullを指し示すような方法はありません。

Answer 5

この場合、指定されたノードが最後のノードであるかどうかをチェックするプログラムが必要です。

void delete_node(node* node1) 
{ 
    node* search=head; 
    if(node1==head) 
    { 
     head=head->next; 
     search->next=NULL; 
     node1->next=NULL; 
    } 
    while(search->next != node1) 
     search=search->next; 
    if(node1->next==NULL) 
    { 
     search->next=NULL; 
    } 
    else 
    { 
     search->next=node1->next; 
     node1->next=NULL; 
    } 
    delete node1; 
} 

Answer 6

public void removeNode(Node node){ 

     /* if no node return null */ 
     if(node==null) return; 

     /* if only 1 node then delete node */ 
     if(node.getNext()==null) { 
      node = null; 
      return ; 
     } 

     /* copy next node data to this node */ 
     node.data = node.getNext().data(); 

     /* store the next next node */ 
     Node second = node.getNext().getNext(); 

     /* remove next node */ 
     removeNode(node.getNext()); 

     /* set the copied node as next */ 
     node.setNext(second); 
    } 

Answer 7

void deleteNode(Node * ptr) 
{ 
    Node *temp = ptr; 
    ptr = ptr->next; 
    temp->data = ptr->data; 
    temp->next = ptr->next; 
    free(ptr); 
} 

は、我々はシングルリンクリスト逆方向を横断することができません。ノードを削除すると、そのメモリが解放されます。次のノードの内容を指定されたポインタ（メモリアドレス）にコピーし、次のノードを解放します。それはあなたの問題を解決するだろう..ありがとう..