下面是交换节点而不改变数据的代码。我想知道是否需要交换节点的下一个指针？交换当前节点不会交换下一个指针吗？为什么？
void swapNodes(Node** head_ref, int x, int y)
{
// Nothing to do if x and y are same
if (x == y)
return;
Node **a = NULL, **b = NULL;
// search for x and y in the linked list
// and store therir pointer in a and b
while (*head_ref) {
if ((*head_ref)->data == x) {
a = head_ref;
}
else if ((*head_ref)->data == y) {
b = head_ref;
}
head_ref = &((*head_ref)->next);
}
// if we have found both a and b
// in the linked list swap current
// pointer and next pointer of these
if (a && b) {
swap(*a, *b);
swap(((*a)->next), ((*b)->next));
}
}
void swap(Node*& a, Node*& b)
{
Node* temp = a;
a = b;
b = temp;
}谢谢你。
2条答案
按热度按时间mepcadol1#
是否需要交换节点的下一个指针？
是的，这是必需的，因为原始节点出现在列表的不同位置。
交换当前节点不会交换下一个指针吗？
是的，交换当前节点并不交换下一个指针。交换当前节点意味着只交换指向当前节点的指针。
例如，考虑列表
假设您需要交换节点B和D。那么您将得到
所以在第一次交换之后，节点A指向节点D，但是节点D“指向”nullptr。如果接下来不交换它们的数据成员，节点B和C将丢失。
因此，接下来还需要交换它们的数据成员
结果你会得到
n7taea2i2#
交换当前节点是不够的。
当交换a和B时，它们的地址会改变，因此它们在列表中的位置将被替换
但您不更改每个节点的内部字段。
节点图示：
阿-阿-阿-阿
我们取节点a和c。
a-〉下一个== &B（真）
c-〉下一个== &d（真）
如果我们像这样交换节点：
c- B -a- d
节点c和节点a的地址将更改，但列表看起来是相同的，因为它们的-〉next值不会更改
如果我们也交换-〉next的值，那么这个列表就真的被交换了