在C 中交換兩個ListNode*

請幫忙，我完全迷失在這里。這是 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;
    }
};

uj5u.com熱心網友回復：

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);            
        }

原始答案??

        if(head!=nullptr and head->next!=nullptr){
            auto previous = head, current = head->next;
            previous->next = current->next; // previous->next = head->next->next
            current->next = previous->next->next; // current->next = head->next->next->next

            previous->next->next = current;
            
            recurse(current);            
        }

在這個if分支中，您只檢查了head和head->next有效。

head->next->next->next但是，您稍后會嘗試呼叫。由于head->next->nextcan be nullptr，您的程式將在此處停止。

你可以在leetcode平臺找到合適的解決方案，這里我只回復一下為什么這段代碼不起作用。

uj5u.com熱心網友回復：

謝謝tieway59，你是對的，我只是自己想通了。我錯過了對head->next->nextin if blockof recursefunction 的另一項驗證。這是我的作業代碼：

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;
    }
};

uj5u.com熱心網友回復：

要交換串列的兩個現有相鄰節點，無需像您一樣創建新節點

auto front = new ListNode(0, head);

否則會出現記憶體泄漏。

相反，您需要通過參考傳遞指向節點的指標。

std::swapC 庫中已經有可以在遞回函式中使用的標準函式。

這是一個演示程式。

#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 * &current )
{
    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

標籤：C 递归 单链表 交换 函数定义

上一篇：存在回圈時繪制遞回DFS？

下一篇：如果使用不同的引數連續兩次呼叫遞回函式，則會出現錯誤的結果