C++で連結リストの隣接ノードをペア単位で入れ替えるプログラム

連結リストが与えられたとき、隣り合う2つのノード(ペア)をすべて入れ替え、その結果の先頭ノード(head)を返すことを考えます。ここでの重要な制約は、ノードが持つ値を変更してはならないという点です。入れ替えられるのはノード自体(ポインタのつながり)のみです。例えば、リストが [1,2,3,4] の場合、実行結果は [2,1,4,3] となります。

解決のためのアルゴリズム

この問題は、以下の手順に従って解くことができます。

• head が存在しない場合は、head をそのまま返します。
• first := head、second := head の次のノードとし、値 -1 を持つ新しいノード dummy を作成します。
• dummy の next を first に設定し、prev := dummy とします。
• second が NULL でない限り、以下を繰り返します。
  • temp := second の次のノード
  • first の next を second の次のノードに設定
  • second の next を first に設定
  • prev の next を second に設定
  • prev := first と更新
  • temp が NULL でなければ、first := temp、second := temp の次のノードとして処理を続行。NULL の場合はループを抜けます。
• 最後に dummy の next を返します。

それでは、実際の実装を見て理解を深めましょう。

サンプルコード(C++)

#include <bits/stdc++.h>
using namespace std;
class ListNode{
public:
    int val;
    ListNode *next;
    ListNode(int data){
        val = data;
        next = NULL;
    }
};
ListNode *make_list(vector<int> v){
    ListNode *head = new ListNode(v[0]);
    for(int i = 1; i<v.size(); i++){
        ListNode *ptr = head;
        while(ptr->next != NULL){
            ptr = ptr->next;
        }
        ptr->next = new ListNode(v[i]);
    }
    return head;
}
void print_list(ListNode *head){
    ListNode *ptr = head;
    cout << "[";
    while(ptr->next){
        cout << ptr->val << ", ";
        ptr = ptr->next;
    }
    cout << "]" << endl;
}
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head)return head;
        ListNode* first= head;
        ListNode* second = head->next;
        ListNode* dummy = new ListNode(-1);
        dummy->next = first;
        ListNode* prev = dummy;
        while(second){
            ListNode* temp = second->next;
            first->next = second->next;
            second->next = first;
            prev->next = second;
            prev = first;
            if(temp){
                first = temp;
                second = temp ->next;
            }
            else break;
        }
        return dummy->next;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    ListNode *head = make_list(v);
    print_list(ob.swapPairs(head));
}

入力

{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}

出力

[2, 1, 4, 3, 6, 5, 8, 7, 10, 9, 12, 11, 14, 13]

このように、ダミーノードを活用して prev・first・second の3つのポインタを操作することで、ノードの値を一切変更せずに、隣接ノード同士を効率的に入れ替えることができます。計算量は O(n)、必要な追加メモリは O(1) です。