c++ - 交换链表的相邻元素

Question

下面是我递归交换链表相邻元素的代码。交换后我丢失了指向每个第二个元素的指针。输入是 1->2->3->4->5->6->7，我期望输出 2->1->4->3->6->5->7，但我的输出是 1->3->5->7。

void nodelist::swap(node* head)
{

    node* temp = head->next;
    if (head->next!= nullptr)
    {
        node* temp2 = temp->next;
        temp->next = head;
        head->next = temp2;
        head = head->next; 
        temp = nullptr;
        temp2 = nullptr;
        swap(head);
    }
}

任何帮助将不胜感激，在此先感谢。

Answer 1

实际上只交换节点的数据成员就足够了。不需要自己交换指针。

不过，如果使用您的方法，那么该函数可能看起来像

void SwapList( node *head )
{
    if ( head != nullptr && head->next != nullptr )
    {
        node *next = head->next;
        std::swap( *head, *next );
        std::swap( head->next, next->next );

        SwapList( head->next->next );
    }
}

这是一个演示程序

#include <iostream>
#include <utility>

struct node
{
    int value;
    node *next;
};

node * AddNode( node *head, int value )
{
    head = new node { value, head };

    return head;
}

void PrintList( node *head )
{
    for ( ; head != nullptr; head = head->next )
    {
        std::cout << head->value << ' ';
    }
}

void SwapList( node *head )
{
    if ( head != nullptr && head->next != nullptr )
    {
        node *next = head->next;
        std::swap( *head, *next );
        std::swap( head->next, next->next );

        SwapList( head->next->next );
    }
}

int main() 
{
    node *head = nullptr;

    for ( int i = 10; i != 0; )
    {
        head = AddNode( head, --i );
    }

    PrintList( head );
    std::cout << std::endl;

    SwapList( head );

    PrintList( head );
    std::cout << std::endl;

    return 0;
}

输出是

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

您可以将显示的函数用作函数的模板(或基础)。