当指向前一个节点的指针不可用时，从单个链接列表中删除中间节点
是否有可能删除单链表中的一个中间节点，当我们唯一可用的信息是指向要删除的节点的指针，而不是指向前一个节点的指针？删除之后，前一个节点应该指向下一个节点删除节点。
这绝对是一个测验，而不是一个真正的问题。 但是，如果我们可以做一些假设，那么可以在O（1）的时间内解决。 要做到这一点，列表指向的限制必须是可复制的。 该algorithm如下：
我们有一个如下所示的列表：… – >节点（i-1） – >节点（i） – >节点（i + 1） – > …我们需要删除节点（i）。
- 从节点（i + 1）到节点（i）复制数据（不是指针，数据本身），列表将如下所示：… – >节点（i-1） – >节点（i + 1） – >节点（i + 1） – > …
- 将第二个节点（i + 1）的NEXT复制到临时variables中。
- 现在删除第二个节点（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; } 麦克风。
我们假设一个结构清单
A→B→C→D
如果你只有一个指向B的指针并想删除它，你可以做类似的事情
tempList = B->next; *B = *tempList; free(tempList);
这个清单会看起来像
A – > B – > D
但是B会保存C的旧内容，从而有效地删除B中的内容。如果某个其他代码正在持有一个指向C的指针，则这将不起作用。如果您试图删除节点D，则这也不起作用。如果你想要做这样的操作，你需要build立一个虚拟的尾节点，这个虚拟的尾节点不是真的被使用，所以你保证没有有用的节点会有一个NULL下一个指针。 这对于存储在节点中的数据量很小的列表也更好。 像一个结构
struct List { struct List *next; MyData *data; };
会没事的，但一个地方
struct HeavyList { struct HeavyList *next; char data[8192]; };
会有点累赘。
不可能。
有黑客模仿删除。
但是没有一个会实际删除指针指向的节点。
如果您有外部指针指向列表中的节点，删除以下节点并将其内容复制到要删除的实际节点的stream行解决scheme具有副作用，在这种情况下，指向下一个节点的外部指针将变为悬挂。
一种方法是为数据插入一个空值。 每当遍历列表时，都会跟踪前一个节点。 如果find空数据，则修正列表，然后转到下一个节点。
最好的办法是将下一个节点的数据拷贝到要删除的节点中，将节点的下一个指针设置为下一个节点的下一个指针，并删除下一个节点。
指向待删除节点的外部指针的问题，同样适用于下一个节点。 考虑下面的链表：
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，并使用较早的方法，则外部指针的问题仍然存在。
最初的build议是改变：
a – > b – > c
至：
a – >，c
如果你保留周围的信息，比如一个从节点地址到下一个节点的地址的映射，那么你可以在下次修复链时遍历列表。 如果需要在下一次遍历之前删除多个项目，则需要跟踪删除的顺序（即更改列表）。
标准的解决scheme是考虑其他数据结构，如跳过列表。
也许做一个软删除？ （即，在节点上设置“已删除”标志）。如果需要，可以稍后清理列表。
我很欣赏这个解决scheme的独创性（删除下一个节点），但是它不能回答问题的问题。 如果这是实际的解决scheme，则正确的问题应该是“从链表中删除包含在指针所在节点中的VALUE”。 但是，当然，正确的问题给你一个解决scheme的提示。 这个问题的制定是为了混淆这个人（事实上这个人发生在我身上，尤其是因为面试官甚至没有提到这个节点在中间）。
不是，如果你想保持列表的可移植性。 您需要更新前一个节点以链接到下一个节点。
在这种情况下，最后怎么样？ 你想要做什么，让你问这个问题？
你将不得不在列表中寻找前一个节点。 一般会删除O（n ** 2）。 如果您是执行删除的唯一代码，则可以在实践中通过caching前一个节点并在那里开始search来做得更好，但这是否有帮助取决于删除模式。
特定
A→B→C→D
和一个指向项目B的指针，你会删除它
1.释放属于B成员的任何内存
2.将C的内容复制到B（这包括它的“下一个”指针）
3.删除整个项目C.
当然，你必须小心边缘情况，例如在一个项目的列表上工作。
现在有了B的地方，你有了C，而曾经是C的存储被释放了。
是的，但你不能脱钩。 如果你不关心腐败的内存，继续;-)
是的，但是删除后，您的列表将被打破。
在这个特定的情况下，再次遍历列表并获取该指针！ 一般来说，如果你问这个问题，你可能在做什么存在一个错误。
为了到达上一个列表项目，您需要从头开始遍历列表，直到find一个指向您当前项目的next指针的条目。 然后你会得到一个指向你必须修改的项目的指针，从列表中删除当前项目 – 只需将previous->next设置为current->next然后删除current 。
编辑：Kimbo击败了我不到一分钟！
你可以做延迟的脱钩，在那里你可以用一个标志设置脱离列表的节点，然后在下一个适当的遍历中删除它们。 设置为脱钩的节点需要由抓取列表的代码正确处理。
我想你也可以从头开始遍历列表，直到find指向列表中的项目的东西。 几乎没有最佳的，但至less比延迟脱钩更好的主意。
一般来说，你应该知道指向你刚才来自的项目的指针，你应该通过它。
（编辑：Ick，随着我花时间写出一个完整的答案，三个gazillion人覆盖了几乎所有我要提到的要点:(）
唯一明智的做法是用两个指针遍历列表，直到前导符find要删除的节点，然后使用尾随指针更新下一个字段。
如果您想要从列表中有效地删除随机项目，则需要双重链接。 如果你想从列表的头部获取项目并将其添加到尾部，则不需要双重链接整个列表。 单独链接列表，但将列表中最后一个项目的下一个字段指向列表中的第一个项目。 然后让列表“头”指向尾部项目（而不是头部）。 然后很容易添加到列表的尾部或从头部删除。
你有名单的头，对吗？ 你只是遍历它。
假设你的列表是由“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;
下面的代码会创build一个LL，然后让n用户给指向要删除的节点的指针。 它会删除后删除列表。删除节点后，删除删除的节点，然后删除下一个节点。 即
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; }
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; } }
如果你有一个链接列表A→B→C→D和一个指向节点B的指针。如果你必须删除这个节点，你可以将节点C的内容复制到B中，将节点D中的内容复制到C中并删除D.但是如果是单向链表，我们不能删除节点，因为如果这样做，节点A也会丢失。 虽然双向链表的情况下可以回溯到A。
我对吗？
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; } }
这是我放在一起的一段代码，它执行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); }
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 }
