40

前のノードへのポインターではなく、削除するノードへのポインターしか入手できない場合、単一のリンクされたリストの中間ノードを削除することは可能ですか?削除後、前のノードは次のノードを指す必要があります。ノードを削除しました。

4

24 に答える 24

87

それは本当の問題というよりは間違いなくクイズです。しかし、何らかの仮定をすることが許されれば、それはO（1）時間で解くことができます。そのためには、リストが指す制限をコピー可能にする必要があります。アルゴリズムは次のとおりです。

次のようなリストがあります：...-> Node（i-1）-> Node（i）-> Node（i + 1）-> ...そしてNode（i）を削除する必要があります。

  1. データ（ポインタではなく、データ自体）をNode（i + 1）からNode（i）にコピーすると、リストは次のようになります。...-> Node（i-1）-> Node（i + 1）->ノード（i + 1）->..。
  2. 2番目のノード（i + 1）のNEXTを一時変数にコピーします。
  3. 次に、2番目のノード（i + 1）を削除します。前のノードへのポインターは必要ありません。

擬似コード：

void delete_node(Node* pNode)
{
    pNode->Data = pNode->Next->Data;  // Assume that SData::operator=(SData&) exists.
    Node* pTemp = pNode->Next->Next;
    delete(pNode->Next);
    pNode->Next = pTemp;
}

マイク。

于 2008-09-16T04:14:01.703 に答える
26

構造を持つリストを想定しましょう

A-> B-> C-> D

Bへのポインタしかなく、それを削除したい場合は、次のようにすることができます。

tempList = B->next;
*B = *tempList;
free(tempList);

リストは次のようになります

A-> B-> D

ただし、BはCの古い内容を保持し、Bにあったものを効果的に削除します。これは、他のコードがCへのポインターを保持している場合は機能しません。また、ノードDを削除しようとした場合も機能しません。この種の操作を実行する場合は、実際には使用されていないダミーのテールノードを使用してリストを作成する必要があります。これにより、有用なノードに次のポインターがNULLにならないことが保証されます。これは、ノードに格納されるデータの量が少ないリストにも適しています。のような構造

struct List { struct List *next; MyData *data; };

大丈夫ですが、

struct HeavyList { struct HeavyList *next; char data[8192]; };

少し面倒です。

于 2008-09-16T04:06:00.133 に答える
11

ありえない。

削除を模倣するハックがあります。

ただし、ポインターが指しているノードを実際に削除することはありません。

次のノードを削除し、その内容を削除する実際のノードにコピーするという一般的な解決策には、リスト内のノードを指す外部ポインターがある場合に副作用があり、その場合、次のノードを指す外部ポインターがぶら下がります。

于 2010-12-28T11:07:54.410 に答える
5

このソリューション (次のノードを削除する) の創意工夫には感謝していますが、問題の質問には答えていません。これが実際の解決策である場合、正しい質問は「リンクされたリストから、ポインターが指定されたノードに含まれる値を削除する」である必要があります。もちろん、正しい質問は解決のヒントを与えてくれます。定式化された問題は、人を混乱させることを目的としています（特にインタビュアーがノードが真ん中にあるとさえ言わなかったので、実際に私に起こりました）。

于 2011-12-15T23:06:30.530 に答える
4

1 つの方法は、データに null を挿入することです。リストをたどるたびに、前のノードを追跡します。null データが見つかった場合は、リストを修正して次のノードに移動します。

于 2008-09-16T03:49:00.517 に答える
3

最初の提案は、次のように変換することでした。

a -> b -> c

に：

a ->, c

たとえば、ノードのアドレスから次のノードのアドレスへのマップなど、情報を保持している場合は、次回チェーンを修正してリストをトラバースできます。次の走査の前に複数のアイテムを削除する必要がある場合は、削除の順序を追跡する必要があります (つまり、変更リスト)。

標準的な解決策は、スキップ リストなどの他のデータ構造を考慮することです。

于 2008-09-16T03:46:49.697 に答える
3

たぶん、ソフト削除を行いますか？(つまり、ノードに「削除済み」フラグを設定します) 必要に応じて、後でリストをクリーンアップできます。

于 2008-09-16T03:48:21.347 に答える
1

与えられた

A-> B-> C-> D

たとえば、アイテムBへのポインタは、1。B
のメンバーに属するメモリを解放します
。2。Cの内容をBにコピーします（これには「次の」ポインタが含まれます）
。3。アイテムC全体を削除します。

もちろん、1つのアイテムのリストで作業するなど、エッジケースに注意する必要があります。

これでBがあった場所に、Cがあり、以前はCであったストレージが解放されます。

于 2008-09-16T04:33:06.807 に答える
1

リストのトラバーサビリティを維持したい場合はそうではありません。次のノードにリンクするには、前のノードを更新する必要があります。

とにかく、どうやってこのような状況に陥ったのですか？この質問をするために何をしようとしていますか?

于 2008-09-16T03:43:27.097 に答える
1

前のノードを見つけるには、リストを下に移動する必要があります。これにより、一般的に O(n**2) の削除が行われます。削除を行う唯一のコードである場合は、前のノードをキャッシュしてそこから検索を開始することで実際にうまくいくかもしれませんが、これが役立つかどうかは削除のパターンによって異なります。

于 2008-09-16T03:47:31.067 に答える
0

これを行う唯一の賢明な方法は、先頭のノードが削除するノードを見つけるまで、いくつかのポインターを使用してリストをトラバースし、末尾のポインターを使用して次のフィールドを更新することです。

リストからランダムなアイテムを効率的に削除したい場合は、二重にリンクする必要があります。ただし、リストの先頭からアイテムを取り出して末尾に追加する場合は、リスト全体を二重にリンクする必要はありません。リストを単独でリンクしますが、リストの最後のアイテムの次のフィールドがリストの最初のアイテムを指すようにします。次に、リストの「ヘッド」がテールアイテム（ヘッドではない）を指すようにします。そうすれば、リストの末尾に追加したり、先頭から削除したりするのは簡単です。

于 2008-09-16T03:58:23.537 に答える
0

これは私がまとめたコードの一部であり、OPが要求していたことを実行し、リストの最後の要素を削除することもできます（最も洗練された方法ではありませんが、実行されます）。リンクリストの使い方を学びながら書いた。それが役に立てば幸い。

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <string>

using namespace std;


struct node
{
    int nodeID;
    node *next;
};

void printList(node* p_nodeList, int removeID);
void removeNode(node* p_nodeList, int nodeID);
void removeLastNode(node* p_nodeList, int nodeID ,node* p_lastNode);

node* addNewNode(node* p_nodeList, int id)
{
    node* p_node = new node;
    p_node->nodeID = id;
    p_node->next = p_nodeList;
    return p_node;
}

int main()
{
    node* p_nodeList = NULL;
    int nodeID = 1;
    int removeID;
    int listLength;
    cout << "Pick a list length: ";
    cin >> listLength;
    for (int i = 0; i < listLength; i++)
    {
        p_nodeList = addNewNode(p_nodeList, nodeID);
        nodeID++;
    }
    cout << "Pick a node from 1 to " << listLength << " to remove: ";
    cin >> removeID;
    while (removeID <= 0 || removeID > listLength)
    {
        if (removeID == 0)
        {
            return 0;
        }
        cout << "Please pick a number from 1 to " << listLength << ": ";
        cin >> removeID;
    }
    removeNode(p_nodeList, removeID);
    printList(p_nodeList, removeID);
}

void printList(node* p_nodeList, int removeID)
{
    node* p_currentNode = p_nodeList;
    if (p_currentNode != NULL)
    {
        p_currentNode = p_currentNode->next;
        printList(p_currentNode, removeID);
        if (removeID != 1)
        {
            if (p_nodeList->nodeID != 1)
            {
                cout << ", ";
            }

            cout << p_nodeList->nodeID;
        }
        else
        {
            if (p_nodeList->nodeID !=2)
            {
                cout << ", ";
            }
            cout << p_nodeList->nodeID;
        }
    }
}

void removeNode(node* p_nodeList, int nodeID)
{
    node* p_currentNode = p_nodeList;
    if (p_currentNode->nodeID == nodeID)
    {
        if(p_currentNode->next != NULL)
        {
            p_currentNode->nodeID = p_currentNode->next->nodeID;
            node* p_temp = p_currentNode->next->next;
            delete(p_currentNode->next);
            p_currentNode->next = p_temp;
        }
        else
        {
            delete(p_currentNode);
        }
    }
    else if(p_currentNode->next->next == NULL)
    {
        removeLastNode(p_currentNode->next, nodeID, p_currentNode);
    }
    else
    {
        removeNode(p_currentNode->next, nodeID);
    }
}

void removeLastNode(node* p_nodeList, int nodeID ,node* p_lastNode)
{
    node* p_currentNode = p_nodeList;
    p_lastNode->next = NULL;
    delete (p_currentNode);
}
于 2013-03-12T08:27:18.727 に答える
0

あなたはリストの先頭にいますよね？あなたはそれを横断するだけです。

リストが「head」とそれを削除するノード「del」によってポイントされているとしましょう。

Cスタイルの擬似コード（ドットはCでは->になります）：

prev = head
next = prev.link

while(next != null)
{
  if(next == del)
  {
    prev.link = next.link;
    free(del);
    del = null;
    return 0;
  }
  prev = next;
  next = next.link;
}

return 1;
于 2008-09-16T04:09:15.587 に答える
0

次のコードは LL, n を作成し、ユーザーに削除するノードへのポインターを与えるように求めます。削除後にリストを出力します。削除するノードの後に​​ノードをコピーし、削除するノードの上にコピーしてから、削除するノードの次のノードを削除するのと同じことを行います。すなわち

あいうえお

c を b にコピーして c を解放し、結果が

acd

struct node  
{
    int data;
    struct node *link;
 };

void populate(struct node **,int);

void delete(struct node **);

void printlist(struct node **);

void populate(struct node **n,int num)
{

    struct node *temp,*t;
    if(*n==NULL)
    {
        t=*n;
        t=malloc(sizeof(struct node));
        t->data=num;
        t->link=NULL;
        *n=t;
    }
    else
    {
        t=*n;
        temp=malloc(sizeof(struct node));
        while(t->link!=NULL)
            t=t->link;
        temp->data=num;
        temp->link=NULL;
        t->link=temp;
    }
}

void printlist(struct node **n)
{
    struct node *t;
    t=*n;
    if(t==NULL)
        printf("\nEmpty list");

    while(t!=NULL)
    {
        printf("\n%d",t->data);
        printf("\t%u address=",t);
        t=t->link;
    }
}


void delete(struct node **n)
{
    struct node *temp,*t;
    temp=*n;
    temp->data=temp->link->data;
    t=temp->link;
    temp->link=temp->link->link;
    free(t);
}    

int main()
{
    struct node *ty,*todelete;
    ty=NULL;
    populate(&ty,1);
    populate(&ty,2);
    populate(&ty,13);
    populate(&ty,14);
    populate(&ty,12);
    populate(&ty,19);

    printf("\nlist b4 delete\n");
    printlist(&ty);

    printf("\nEnter node pointer to delete the node====");
    scanf("%u",&todelete);
    delete(&todelete);

    printf("\nlist after delete\n");
    printlist(&ty);

    return 0;
}
于 2009-06-16T11:08:48.577 に答える
0

はい。ただし、リンクを解除することはできません。メモリの破損を気にしない場合は、先に進んでください;-)

于 2008-09-16T03:42:03.030 に答える
0

リンクされたリスト A -> B -> C -> D とノード B へのポインターがあるとします。このノードを削除する必要がある場合は、ノード C の内容を B にコピーし、ノード D を C にコピーして、D を削除することができます。単独でリンクされたリストの場合、ノードをそのまま削除することはできません。削除すると、ノード A も失われるからです。ただし、二重リンク リストの場合は A に戻ることができます。

私は正しいですか？

于 2010-09-03T12:25:02.903 に答える
0

はい。ただし、削除するとリストが破損します。

この特定のケースでは、リストをもう一度トラバースして、そのポインターを取得します! 一般的に、あなたがこの質問をしているのであれば、おそらくあなたのやっていることにバグがあるでしょう。

于 2008-09-16T03:45:51.663 に答える
0

next前のリスト アイテムに到達するには、現在のアイテムを指すポインターを含むエントリが見つかるまで、リストを最初からトラバースする必要があります。次に、リストから現在のアイテムを削除するために変更する必要がある各アイテムへのポインターを取得します。単に、次に deleteに設定previous->nextします。current->nextcurrent

編集: Kimbo は 1 分もかからずに私を打ち負かしました!

于 2008-09-16T03:48:17.803 に答える
0

フラグを使用してノードをリストからリンク解除するように設定し、次の適切なトラバーサルでノードを削除する遅延リンク解除を行うことができます。リンクを解除するように設定されたノードは、リストをクロールするコードによって適切に処理される必要があります。

リスト内のアイテムを指すものが見つかるまで、リストを最初からもう一度トラバースすることもできると思います。最適とは言えませんが、少なくとも遅延リンク解除よりもはるかに優れたアイデアです。

一般に、元のアイテムへのポインターを知っている必要があり、それを渡す必要があります。

（編集：いや、完全な回答を入力するのに時間がかかったので、3億人の人々が私が言及しようとしていたほとんどすべてのポイントをカバーしました.:()

于 2008-09-16T03:50:57.983 に答える
0 
void delself(list *list)
{
   /*if we got a pointer to itself how to remove it...*/
   int n;

   printf("Enter the num:");

   scanf("%d",&n);

   while(list->next!=NULL)
   {
       if(list->number==n) /*now pointer in node itself*/
       {
           list->number=list->next->number;
           /*copy all(name,rollnum,mark..) data of next to current, disconect its next*/
           list->next=list->next->next;
       }
       list=list->next;
   }
}
于 2010-02-21T17:11:11.293 に答える
0 
void delself(list *list)
{
   /*if we got a pointer to itself how to remove it...*/
   int n;

   printf("Enter the num:");
   scanf("%d",&n);

   while(list->next!=NULL)
   {
      if(list->number==n) /*now pointer in node itself*/
      {
         list->number=list->next->number;   /*copy all(name,rollnum,mark..)
                             data of next to current, disconnect its next*/
         list->next=list->next->next;
      }
      list=list->next;
   }
}
于 2010-02-21T17:20:07.383 に答える
-1 
Void deleteMidddle(Node* head)
{
     Node* slow_ptr = head;
     Node* fast_ptr = head;
     Node* tmp = head;
     while(slow_ptr->next != NULL && fast_ptr->next != NULL)
     {
        tmp = slow_ptr;
        slow_ptr = slow_ptr->next;
        fast_ptr = fast_ptr->next->next;
     }
     tmp->next = slow_ptr->next;
     free(slow_ptr);
    enter code here

}
于 2012-11-23T02:56:54.767 に答える