40

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

4

24 回答 24

87

It's definitely more a quiz rather than a real problem. However, if we are allowed to make some assumption, it can be solved in O(1) time. To do it, the strictures the list points to must be copyable. The algorithm is as the following:

We have a list looking like: ... -> Node(i-1) -> Node(i) -> Node(i+1) -> ... and we need to delete Node(i).

  1. Copy data (not pointer, the data itself) from Node(i+1) to Node(i), the list will look like: ... -> Node(i-1) -> Node(i+1) -> Node(i+1) -> ...
  2. Copy the NEXT of second Node(i+1) into a temporary variable.
  3. Now Delete the second Node(i+1), it doesn't require pointer to the previous node.

Pseudocode:

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

Mike.

于 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，它也将不起作用。如果你想做这种操作，你需要用一个没有真正使用的虚拟尾节点来构建列表，这样你就可以保证没有有用的节点会有一个空的下一个指针。这对于存储在节点中的数据量很小的列表也更有效。像这样的结构

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

我很欣赏这个解决方案的独创性（删除下一个节点），但它没有回答问题的问题。如果这是实际的解决方案，那么正确的问题应该是“从链表中删除包含在给定指针的节点中的 VALUE”。但是，当然，正确的问题会给你一个解决方案的提示。制定的问题是为了迷惑人（这实际上发生在我身上，特别是因为面试官甚至没有提到节点在中间）。

于 2011-12-15T23:06:30.530 回答
4

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

于 2008-09-16T03:49:00.517 回答
4

最好的做法还是将next节点的数据复制到要删除的节点中，将该节点的next指针设置为next节点的next指针，然后删除next节点。

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

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，并且使用前面的方法，外部指针的问题仍然存在。

于 2012-07-18T05:22:13.380 回答
3

最初的建议是改造：

a -> b -> c

至：

一个->，c

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

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

于 2008-09-16T03:46:49.697 回答
3

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

于 2008-09-16T03:48:21.347 回答
1

如果您想保持列表的可遍历性，则不是。您需要更新前一个节点以链接到下一个节点。

无论如何，你是怎么落到这种境地的？你想做什么让你问这个问题？

于 2008-09-16T03:43:27.097 回答
1

您必须沿着列表向下移动才能找到上一个节点。这将使删除通常为 O(n**2)。如果您是唯一执行删除的代码，您可以通过缓存前一个节点并在那里开始搜索来在实践中做得更好，但这是否有帮助取决于删除的模式。

于 2008-09-16T03:47:31.067 回答
1

Given

A -> B -> C -> D

and a pointer to, say, item B, you would delete it by
1. free any memory belonging to members of B
2. copy the contents of C into B (this includes its "next" pointer)
3. delete the entire item C

Of course, you'll have to be careful about edge cases, such as working on lists of one item.

Now where there was B, you have C and the storage that used to be C is freed.

于 2008-09-16T04:33:06.807 回答
1

考虑下面的链表

1 -> 2 -> 3 -> 空

指向节点 2 的指针被指定为“ptr”。

我们可以有如下所示的伪代码：

struct node* temp = ptr->next;
ptr->data = temp->data;
ptr->next = temp->next;
free(temp);
于 2019-09-20T17:17:56.363 回答
0

是的，但你不能取消链接。如果您不关心损坏内存，请继续；-)

于 2008-09-16T03:42:03.030 回答
0

是的，但您的列表将在您删除后被破坏。

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

于 2008-09-16T03:45:51.663 回答
0

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

编辑：Kimbo 以不到一分钟的时间击败了我！

于 2008-09-16T03:48:17.803 回答
0

您可以延迟取消链接，您可以使用标志将节点从列表中取消链接，然后在下一次正确遍历时将其删除。设置为断开链接的节点需要由爬取列表的代码正确处理。

我想您也可以从头开始再次遍历列表，直到找到指向列表中您的项目的东西。几乎不是最优的，但至少比延迟分离要好得多。

一般来说，您应该知道指向您刚刚来自的项目的指针，并且应该传递它。

（编辑：Ick，随着我输入完整答案的时间，三亿人几乎涵盖了我要提到的所有要点。:()

于 2008-09-16T03:50:57.983 回答
0

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

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

于 2008-09-16T03:58:23.537 回答
0

You have the head of the list, right? You just traverse it.

Let's say that your list is pointed to by "head" and the node to delete it "del".

C style pseudo-code (dots would be -> in 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

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

我对吗？

于 2010-09-03T12:25:02.903 回答
0

下面的代码将创建一个 LL，n 然后要求用户将指针指向要删除的节点。它将在删除后打印列表它的作用与通过复制要删除的节点之后的节点，覆盖要删除的节点然后删除要删除的节点的下一个节点来完成相同的操作。IE

A B C D

将 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

这是我放在一起的一段代码，它可以满足 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 
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 回答