简单链表与下一个>下一个交换

Question

当我试图为简单链表中的两个节点构造交换函数时，我遇到了一个奇怪的事件。

包含 5 个节点的列表。我通过了第一个节点，第三个节点：

//list is the head of the linked list
interchange(list, list->pNext->pNext);

以下是导致问题的唯一说明，以使其更简单：

void interchange(SList*& p, SList*& q) {
p->pNext->pNext = q->pNext->pNext;
}

我的问题是，根据我对编码的理解，相等操作中的左成员得到右成员的值。 p->pNext->pNext 采用正确的值。但是名为"q"的指针将指向这条指令之后的q->pNext->pNext。

有才华横溢的人能对此有所了解吗？ 提前谢谢你们。

Answer 1

考虑对interchange(SList*& p, SList*& q)的调用。

你传递它的值p = list作为引用，它的孙子q = list->pNext->pNext，也作为参考。

当您为p->pNext->pNext分配q->pNext->pNext的值时，您正在修改list->pNext->pNext以指向list->pNext->pNext->pNext->pNext。

由于q = list->pNext->pNext作为参考，因此您还将修改q以指向list->pNext->pNext->pNext->pNext;q毕竟基本上是更名的list->pNext->pNext。

如果将函数签名更改为void interchange(SList* p, SList* q)则不会修改q，因为它现在只是一个基本的指针，当您更改p->pNext->pNext时。

Answer 2

您没有显示列表定义，但该函数可以如下所示

void interchange( SList*& p, SList*& q ) 
{
std::swap( p, q );
std::swap( p->next, q->next );
}

如演示程序所示。

#include <iostream>
#include <utility>
struct SList
{
int data;
SList *next;
};
void push_front( SList * &head, int data )
{
SList *tmp = new SList { data, head };
head = tmp;
}
std::ostream & display( SList * &head, std::ostream &os = std::cout )
{
for ( const SList *current = head; current != nullptr; current = current->next )
{
os << current->data << ' ';
}
return os;
}
void interchange( SList*& p, SList*& q ) 
{
std::swap( p, q );
std::swap( p->next, q->next );
}
int main() 
{
SList *head = nullptr;
const int N = 10;
for ( int i = N; i != 0; )
{
push_front( head, --i );
}
display( head ) << std::endl;
interchange( head, head->next->next );  
display( head ) << std::endl;
return 0;
}

程序输出为

0 1 2 3 4 5 6 7 8 9 
2 1 0 3 4 5 6 7 8 9 

Answer 3

这是您当前实现的逻辑

p = list
q = list->pNext->pNext
p->pNext->pNext = q->pNext->pNext
// Same as
list->pNext->pNext = list->pNext->pNext->pNext->pNext
// Before list->A->B->C->D
// After list->A->D

您将指向 B 的指针替换为指向 D 的指针。q仍然指向list->pNext->pNext，现在指向之前list->pNext->pNext->pNext->pNext的D，以前等同于q->pNext->pNext。