在C＆＃x2B;＆＃x2B中交换两个listNode*

Question

请帮忙，我在这里完全迷失了。这是Leetcode问题编号。 24，成对交换节点。 我在筛选中遇到了这个错误。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    void recurse(ListNode* head){
        if(head!=nullptr and head->next!=nullptr){
            auto previous = head, current = head->next;
            previous->next = current->next;
            current->next = previous->next->next;
            previous->next->next = current;
            
            recurse(current);            
        }
    }
public:
    ListNode* swapPairs(ListNode* head) {
        auto front = new ListNode(0, head);
        recurse(front);
        return front->next;
    }
};

Answer 1

upd ：我添加了一些注释来说明OP的正确的解决方案：

        if(head!=nullptr and head->next!=nullptr 
           and head->next->next!=nullptr){
            // p->[c]->[x]->y; swap(c, x); y can be null
            auto previous = head, current = head->next;
            // p->c->x->y
            previous->next = current->next;
            // p->x->y; c->x->y
            current->next = previous->next->next;
            // c->y; p->x->y
            previous->next->next = current;
            // p->x->c->y 
            recurse(current);            
        }

原始答案

Answer 2

谢谢tieway59，您是对的，我只是自己想出的。如果 block recurse 函数，我缺少heack中的下一个的heack的另外一个验证。
这是我的工作代码：

class Solution {
    void recurse(ListNode* head){
        if(head!=nullptr and head->next!=nullptr 
           and head->next->next!=nullptr){

            auto previous = head, current = head->next;
            previous->next = current->next;
            current->next = previous->next->next;
            previous->next->next = current;
            recurse(current);            
        }
    }
public:
    ListNode* swapPairs(ListNode* head){
        auto front = new ListNode(0, head);
        recurse(front);
        return front->next;
    }
};

Answer 3

要交换列表的两个存在的相邻节点，就无需像您这样做的那样创建一个新节点

auto front = new ListNode(0, head);

。

相反，您需要的是通过参考将指针传递给节点。

在C ++库中，已经有标准函数std ::交换可以在您的递归功能中使用。

这是一个演示程序。

#include <iostream>
#include <utility>
#include <functional>

struct ListNode 
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
 };


void clear( ListNode * &head )
{
    while ( head )
    {
        delete std::exchange( head, head->next );
    }
}

void create( ListNode * &head, const int a[], size_t n )
{
    clear( head );

    for ( ListNode **current = &head; n--; current = &( *current )->next )
    {
        *current = new ListNode( *a++ );
    }
}

std::ostream & display( const ListNode * head, std::ostream &os = std::cout )
{
    for ( const ListNode *current = head; current != nullptr; current = current->next )
    {
        os << current->val << " -> ";
    }

    return os << "null";
}

void swap( ListNode * ¤t )
{
    if ( current && current->next )
    {
        ListNode * &next = current->next;
        std::swap( current, next );
        std::swap( current->next, next->next );
        swap( next );
    }
}

int main()
{
    ListNode *head= nullptr;
    const int a[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    create( head, a, sizeof( a ) / sizeof( *a ) );
    display( head ) << '\n';

    swap( head );
    display( head ) << '\n';

    clear( head );
}

程序输出是

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
1 -> 0 -> 3 -> 2 -> 5 -> 4 -> 7 -> 6 -> 9 -> 8 -> null