简单链接列表与next-> next交换

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

你用指向D的指针替换了指向B的指针.q仍然指向list->pNext->pNext，它现在指向D，这是之前等同于list->pNext->pNext->pNext->pNext的q->pNext->pNext。