当指向前一个节点的指针不可用时，从单个链表中删除中间节点-Java 学习之路

当我们可用的唯一信息是指向要删除的节点的指针而不是指向前一节点的指针时，是否可以删除单个链表中的中间节点？删除后，前一节点应指向旁边的节点删除节点 .

23 回答

0

最好的方法仍然是将下一个节点的数据复制到要删除的节点中，将节点的下一个指针设置为下一个节点的下一个指针，然后删除下一个节点 .

指向要删除的节点的外部指针的问题虽然为真，但也适用于下一个节点 . 请考虑以下链接列表：

A-> B-> C-> D-> E-> F和G-> H-> I-> D-> E-> F

如果您必须删除节点C（在第一个链接列表中），通过上述方法，您将在将内容复制到节点C后删除节点D.这将产生以下列表：

A-> B-> D-> E-> F和G-> H-> I->悬空指针 .

如果您完全删除NODE C，结果列表将是：

A-> B-> D-> E-> F和G-> H-> I-> D-> E-> F.

但是，如果要删除节点D，并使用前面的方法，那么外部指针的问题仍然存在 .

回复于 2024-05-03T12:30:42+08:00
0

最初的建议是改造：

a - > b - > c

至：

a - >，c

如果您保留信息，例如，从节点地址到下一个节点的地址，那么您可以在下次遍历列表时修复链 . 如果需要在下次遍历之前删除多个项目，则需要跟踪删除的顺序（即更改列表） .

标准解决方案是考虑其他数据结构，如跳过列表 .

回复于 2024-05-03T12:30:42+08:00
25

也许做一个软删除？（即，在节点上设置“已删除”标志）如果需要，可以稍后清理列表 .

回复于 2024-05-03T12:30:42+08:00
1
这绝对是一个测验，而不是一个真正的问题 . 但是，如果允许我们做出一些假设，可以在O（1）时间内解决 . 要做到这一点，列表指向的限制必须是可复制的 . 算法如下：

我们有一个列表如下：... - > Node（i-1） - > Node（i） - > Node（i 1） - > ...我们需要删除Node（i） .
- 将数据（非指针，数据本身）从节点（i 1）复制到节点（i），列表将如下所示：... - >节点（i-1） - >节点（i 1） - >节点（i 1） - > ...
- 将第二个节点（i 1）的NEXT复制到临时变量中 .
- 现在删除第二个节点（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;
}
```
麦克风 .
回复于 2024-05-03T12:30:42+08:00
3
让我们假设一个结构列表

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]; };
```
会有点累赘 .
回复于 2024-05-03T12:30:42+08:00
0

不可能 .

有些黑客可以模仿删除 .

但是，实际上没有一个会删除指针所指向的节点 .

如果您有 external pointers 指向列表中的节点，则删除 following 节点并将其内容复制到要删除的 actual 节点的流行解决方案会产生副作用，在这种情况下，指向以下节点的外部指针将变为悬空 .

回复于 2024-05-03T12:30:42+08:00
1

一种方法是为数据插入null . 每当遍历列表时，都会跟踪前一个节点 . 如果找到空数据，则修复列表，然后转到下一个节点 .

回复于 2024-05-03T12:30:42+08:00
4

我很欣赏这个解决方案的独创性（删除下一个节点），但它没有回答问题的问题 . 如果这是实际的解决方案，那么正确的问题应该是“从链接列表中删除指定给定指针的节点中包含的VALUE” . 但是，当然，正确的问题可以为您提供解决方案的提示 . 制定这个问题的目的是让人感到困惑（实际上这件事发生在我身上，特别是因为面试官甚至没有提到节点位于中间） .

回复于 2024-05-03T12:30:42+08:00
86

不是，如果你想保持列表的可穿越性 . 您需要更新上一个节点以链接到下一个节点 .

无论如何，你怎么会在这种情况下结束？你想做什么让你问这个问题？

回复于 2024-05-03T12:30:42+08:00
0

您必须沿着列表前进才能找到上一个节点 . 这将使删除一般为O（n ** 2） . 如果您是唯一进行删除的代码，您可以通过缓存上一个节点并在那里开始搜索来做得更好，但这是否有帮助取决于删除的模式 .

回复于 2024-05-03T12:30:42+08:00
11

特定

A - > B - > C - > D.

和一个指向项目B的指针，你会删除它
1.释放属于B成员的任何记忆
2.将C的内容复制到B（这包括它的"next"指针）
3.删除整个项目C.

当然，您必须小心边缘情况，例如处理一个项目的列表 .

现在有B的地方，你有C并且以前存储的C被释放了 .

回复于 2024-05-03T12:30:42+08:00
0

是的，但你不能脱钩 . 如果你不关心腐败记忆，请继续;-)

回复于 2024-05-03T12:30:42+08:00
0

是的，但删除后列表将被破坏 .

在这种特定情况下，再次遍历列表并获取指针！一般来说，如果你问这个问题，可能存在你正在做的事情的错误 .

回复于 2024-05-03T12:30:42+08:00
0

为了到达上一个列表项，您需要从头开始遍历列表，直到找到带有指向当前项的 next 指针的条目 . 然后你必须修改以从列表中删除当前项 - 只需将 previous->next 设置为 current->next 然后删除 current .

编辑：Kimbo不到一分钟就打败了我！

回复于 2024-05-03T12:30:42+08:00
3

您可以使用标志将节点设置为脱离列表，然后在下一次正确的遍历中删除它们，从而延迟脱钩 . 设置为脱链的节点需要由爬网列表的代码正确处理 .

我想您也可以从头开始再次遍历列表，直到找到指向列表中项目的内容 . 几乎没有最佳，但至少比延迟脱钩更好的想法 .

一般来说，你应该知道你刚刚来自的项目的指针，你应该传递它 .

（编辑：Ick，我花了很多时间来输出一个完整的答案，三千万人几乎涵盖了我要提到的所有要点 . :(）

回复于 2024-05-03T12:30:42+08:00
0

唯一明智的方法是使用几个指针遍历列表，直到前导者找到要删除的节点，然后使用尾随指针更新下一个字段 .

如果要有效地从列表中删除随机项，则需要进行双重链接 . 如果您想从列表的头部获取项目并在尾部添加它们，则不需要双重链接整个列表 . 单独链接列表，但使列表中最后一项的下一个字段指向列表中的第一个项目 . 然后将列表“head”指向尾部项目（而不是头部） . 然后很容易添加到列表的尾部或从头部删除 .

回复于 2024-05-03T12:30:42+08:00
1
你有名单的负责人，对吧？你只是遍历它 .

假设您的列表由“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;
```
回复于 2024-05-03T12:30:42+08:00

-1

下面的代码将创建一个LL，n然后要求用户给出要删除的节点的指针 . 它将在删除后打印列表它通过在要删除的节点之后复制节点，在要删除的节点上执行相同的操作，然后删除要删除的节点的下一个节点 . 即

A B C D

将c复制到b并释放c，以便得到结果

A-C-d

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

回复于 2024-05-03T12:30:42+08:00

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

回复于 2024-05-03T12:30:42+08:00

4

如果你有一个链表A - > B - > C - > D和一个指向节点B的指针 . 如果你必须删除这个节点你可以将节点C的内容复制到B，节点D复制到C并删除D.但是我们不能在单链表的情况下删除节点，因为如果我们这样做，节点A也将丢失 . 虽然我们可以在双链表的情况下回溯到A.

我对吗？

回复于 2024-05-03T12:30:42+08:00

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

回复于 2024-05-03T12:30:42+08:00

这是我放在一起执行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);
}

回复于 2024-05-03T12:30:42+08:00

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

}

回复于 2024-05-03T12:30:42+08:00

当指向前一个节点的指针不可用时，从单个链表中删除中间节点

23 回答

相关问题