当我们拥有的唯一可用信息是指向要删除的节点的指针而不是指向上一个节点的指针时，是否可以删除单个链表中的中间节点？删除后，上一个节点应指向下一个节点 删除的节点。
这绝对是测验，而不是实际的问题。但是，如果允许我们做一些假设，则可以在O(1)时间内解决。为此，列表指向的限制必须是可复制的。算法如下：
我们有一个看起来像这样的列表：...-> Node(i-1)-> Node(i)-> Node(i + 1)-> ...，我们需要删除Node(i)。
将数据(不是指针，而是数据本身)从Node(i + 1)复制到Node(i)，列表如下所示：...-> Node(i-1)-> Node(i + 1)->节点(i + 1)-> ...
将第二个Node(i + 1)的NEXT复制到一个临时变量中。
现在删除第二个节点(i + 1)，它不需要指向上一个节点的指针。
伪代码：
1
2
3
4
5
6
7
| 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的指针并想删除它，则可以执行以下操作
1
2
3
| tempList = B->next;
*B = *tempList;
free(tempList); |
该列表将如下所示
A-> B-> D
但是B会保留C的旧内容，从而有效地删除B中的内容。如果其他一些代码持有指向C的指针，则此操作将无效。如果您尝试删除节点D，它也将无效。如果要执行这种操作，则需要使用未真正使用的虚拟尾节点来构建列表，以确保没有有用的节点的下一个指针为NULL。这对于节点中存储的数据量较小的列表也更有效。像这样的结构
1
| struct List { struct List *next; MyData *data; }; |
会好的，但是那是
1
| struct HeavyList { struct HeavyList *next; char data[8192]; }; |
会有点累。
不可能。
有一些模仿删除的技巧。
但是，这些都不会真正删除指针指向的节点。
如果您有指向列表中节点的外部指针，则删除后一个节点并将其内容复制到要删除的实际节点的流行解决方案会有副作用，在这种情况下，指向后一个节点的外部指针将变得悬而未决。
我很欣赏此解决方案的独创性(删除下一个节点)，但是它不能解决问题。如果这是实际的解决方案，则正确的问题应该是"从链接列表中删除在其上给出了指针的节点中包含的VALUE"。但是，当然，正确的问题可以为您提供解决方案的提示。
提出的问题旨在使人感到困惑(实际上这已经发生在我身上，尤其是因为面试官甚至没有提到节点在中间)。
最好的方法仍然是将下一个节点的数据复制到要删除的节点中，将节点的下一个指针设置为下一个节点的下一个指针，然后删除下一个节点。
指向要删除的节点的外部指针的问题虽然为真，但也适用于下一个节点。考虑以下链接列表：
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，并且使用较早的方法，则仍然存在外部指针问题。
一种方法是为数据插入空值。每当遍历列表时，您都会跟踪上一个节点。如果发现空数据，请修复列表，然后转到下一个节点。
最初的建议是进行以下转换：
a-> b-> c
至：
a->，c
如果您保留信息，例如，从节点地址到下一个节点地址的映射，则可以在下次修复链以遍历列表。如果需要在下一次遍历之前删除多个项目，则需要跟踪删除的顺序(即更改列表)。
标准解决方案是考虑其他数据结构，例如跳过列表。
也许要进行软删除？ (即，在节点上设置"已删除"标志)，以后可以根据需要清理列表。
如果您想保持列表的可遍历性，则不需要。您需要更新上一个节点以链接到下一个节点。
无论如何，您怎么会遇到这种情况？您要做什么才能使您提出这个问题？
您必须沿列表前进才能找到上一个节点。这将导致删除一般O(n ** 2)。如果您是唯一执行删除操作的代码，则在实践中可能会做得更好，方法是缓存上一个节点，然后在该位置开始搜索，但这是否有用取决于删除的模式。
给定
A-> B-> C-> D
和指向项目B的指针，您可以通过以下方式将其删除
1.释放属于B成员的任何记忆
2.将C的内容复制到B中(包括其"下一个"指针)
3.删除整个项目C
当然，您必须注意边缘情况，例如处理一项清单。
现在那里有B，您有了C，并且曾经是C的存储已释放。
考虑以下链接列表
1 -> 2 -> 3 -> NULL
Pointer to node 2 is given say"ptr".
我们可以使用如下所示的伪代码：
1
2
3
4
| struct node* temp = ptr->next;
ptr->data = temp->data;
ptr->next = temp->next;
free(temp); |
这是我编写的一段代码，可以完成OP的要求，甚至可以删除列表中的最后一个元素(不是最优雅的方式，但是可以完成)。在学习如何使用链表的同时写了它。希望能帮助到你。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #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);
} |
是的，但是将其删除后，您的列表将被打断。
在这种情况下，再次遍历列表并获得该指针！通常，如果您在问这个问题，那么您所做的事情可能存在错误。
为了到达上一个列表项，您需要从头开始遍历该列表，直到找到带有指向当前项目的next指针的条目。然后，您将具有一个指向每个项目的指针，这些项目需要修改才能从列表中删除当前项目-只需将previous->next设置为current->next，然后删除current。
编辑：Kimbo在不到一分钟的时间内击败了我！
您可以执行延迟的取消链接，在该链接中设置带有标志的要从列表中取消链接的节点，然后在下一次正确遍历时将其删除。设置为取消链接的节点将需要由爬网列表的代码正确处理。
我想您也可以从头开始再次遍历列表，直到找到指向列表中项目的东西为止。这几乎不是最佳选择，但至少比延迟脱链更好。
通常，您应该知道刚来自项目的指针，并且应该将其传递给它。
(编辑：艾克，随着我花了很长时间才给出完整的答案，三个专长的人几乎涵盖了我要提到的所有要点。:()
你是名单的首长吧？您只需遍历它。
假设您的列表指向" head"，删除该节点的节点指向" del"。
C风格的伪代码(点在C中为->)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| 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; |
是的，但是您不能取消链接。如果您不关心内存损坏，请继续;-)
以下代码将创建一个LL，n然后要求用户将指针提供给要删除的节点。删除后将打印列表
它的作用与通过在要删除的节点之后复制节点，在要删除的节点上复制节点，然后删除要删除的节点的下一个节点来执行的操作相同。
即
A B C D
将c复制到b并释放c，这样的结果是
c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
| 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("\
Empty list");
while(t!=NULL)
{
printf("\
%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("\
list b4 delete\
");
printlist(&ty);
printf("\
Enter node pointer to delete the node====");
scanf("%u",&todelete);
delete(&todelete);
printf("\
list after delete\
");
printlist(&ty);
return 0;
} |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 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;
}
} |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 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。
我对吗？
唯一明智的方法是使用几个指针遍历列表，直到前一个找到要删除的节点，然后使用尾随指针更新下一个字段。
如果要有效地从列表中删除随机项目，则需要对其进行双重链接。但是，如果要从列表的开头取出项目，然后在列表的末尾添加它们，则不需要双重链接整个列表。单独链接列表，但使列表上最后一项的下一个字段指向列表上的第一项。然后使列表" head"指向尾项(而不是head)。这样就很容易将其添加到列表的末尾或从头部删除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| 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
} |
