C++で連結リストの要素をペアごとに入れ替える方法（反復法・再帰法）

本記事では、連結リスト内のノードをペアごとに入れ替え、その結果を出力する問題の解き方を解説します。

問題の例

入力 : 1->2->3->4->5->6->NULL
出力 : 2->1->4->3->6->5->NULL

入力 : 1->2->3->4->5->NULL
出力 : 2->1->4->3->5->NULL

入力 : 1->NULL
出力 : 1->NULL

この問題には主に2つのアプローチがあり、どちらも計算量は O(N)（N は連結リストのサイズ）です。ここでは、両方のアプローチを順番に見ていきましょう。

反復法（イテレーティブなアプローチ）

このアプローチでは、連結リストの要素を先頭から順に走査し、NULL に到達するまで隣接する2つのノードのデータを入れ替えていきます。ペアとして扱うには2つのノードが必要なため、ループ条件では「現在のノード」と「次のノード」がどちらも NULL でないことを確認します。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
class Node { // リストのノード
public:
    int data;
    Node* next;
};
void swapPairwise(Node* head){
    Node* temp = head;
    // ペア単位での入れ替えには2ノード必要なため条件をチェック
    while (temp != NULL && temp->next != NULL) {
        swap(temp->data,
            temp->next->data); // データを入れ替える
        temp = temp->next->next; // 次のペアへ移動
    }
}
void push(Node** head_ref, int new_data){ // リストへデータを追加する関数
    Node* new_node = new Node(); // 新しいノードを作成
    new_node->data = new_data;
    new_node->next = (*head_ref); // 先頭を後ろにずらす
    (*head_ref) = new_node; // 新しいノードが先頭になる
}
void printList(Node* node){ // 連結リストを出力するユーティリティ関数
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}
int main(){
    Node* head = NULL;
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    cout << "入れ替え前の連結リスト\n";
    printList(head);
    swapPairwise(head);
    cout << "\n入れ替え後の連結リスト\n";
    printList(head);
    return 0;
}

実行結果

入れ替え前の連結リスト
1 2 3 4 5
入れ替え後の連結リスト
2 1 4 3 5

再帰法（リカーシブなアプローチ）

次に紹介するのは、同じロジックを再帰を使って実装する方法です。反復法と同様に、現在のノードと次のノードが存在する場合にデータを入れ替え、その2つ先のノードに対して自分自身を呼び出すことで処理を進めます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
class Node { // リストのノード
public:
    int data;
    Node* next;
};
void swapPairwise(struct Node* head){
    // 反復法と同じ条件判定
    if (head != NULL && head->next != NULL) {
        swap(head->data, head->next->data); // データを入れ替える
        swapPairwise(head->next->next); // 次のペアへ移動
    }
    return; // 条件を満たさなければ終了
}
void push(Node** head_ref, int new_data){ // リストへデータを追加する関数
    Node* new_node = new Node(); // 新しいノードを作成
    new_node->data = new_data;
    new_node->next = (*head_ref); // 先頭を後ろにずらす
    (*head_ref) = new_node; // 新しいノードが先頭になる
}
void printList(Node* node){ // 連結リストを出力するユーティリティ関数
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
}
int main(){
    Node* head = NULL;
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
    cout << "入れ替え前の連結リスト\n";
    printList(head);
    swapPairwise(head);
    cout << "\n入れ替え後の連結リスト\n";
    printList(head);
    return 0;
}

実行結果

入れ替え前の連結リスト
1 2 3 4 5
入れ替え後の連結リスト
2 1 4 3 5

コードの解説

どちらのアプローチでも、連結リストをペア単位で走査していく点は共通しています。ペアに到達したらその2つのノードのデータを入れ替え、次のペアへと処理を進めます。反復法では while ループでこれを実現し、再帰法では関数の自己呼び出しによって同じことを行っています。

なお、ここではノード自体をつなぎ替えるのではなく、各ノードが持つ「データ」を入れ替える方式を採用しています。そのため実装がシンプルになり、ポインタ操作によるバグも起きにくくなります。ただし、ノードの構造体が大きい場合や、実際にリンク構造を入れ替えることが求められる場合は、ポインタをつなぎ替える方式を検討するとよいでしょう。

まとめ

本記事では、連結リストの要素をペアごとに入れ替える問題を、反復法と再帰法の2通りの方法で解きました。どちらの方法も計算量は O(N)、空間計算量は反復法が O(1)、再帰法は呼び出しスタックの分だけ O(N) となる点が違いです。同じロジックは C、Java、Python など他の言語でも同様に実装できます。皆さんの学習に役立てば幸いです。