C++で連結リストのノードをペアごとに交換する方法

ここでは、連結リスト（リンクリスト）が与えられたとき、隣り合う2つのノードをペアごとに入れ替え、その結果の先頭ノードを返す問題を扱います。重要な制約として、ノードが持つ値（val）を変更することはできず、ノード自体のつながり（ポインタ）だけを操作して入れ替えを行う必要があります。

例えば、リストが [1,2,3,4] の場合、処理後のリストは [2,1,4,3] となります。奇数個の要素がある場合は、最後の1つのノードはそのまま残ります。

アルゴリズムの手順

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

• head が存在しない（NULL の）場合は、そのまま head を返す
• first := head、second := head の次のノード とする。また、値 -1 を持つダミーノード dummy を新しく作成する
• dummy->next := first とし、prev := dummy と初期化する
• second が NULL でない限り、以下を繰り返す
  • temp := second の次のノード を保存しておく
  • first->next := second->next とする
  • second->next := first とする（first と second を入れ替え）
  • prev->next := second とする（前のペアと新しいペアをつなぐ）
  • prev := first と更新する
  • temp が NULL でなければ、first := temp、second := temp->next として次のペアへ進む。そうでなければループを抜ける
• 最後に 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};
   ListNode *head = make_list(v);
   print_list(ob.swapPairs(head));
}

入力

[1,2,3,4,5,6,7,8]

出力

[2,1,4,3,6,5,8,7]

ポイントの解説

この実装の鍵となるのはダミーノード（dummy）の活用です。先頭ノード自体が入れ替わるため、戻り値となる新しい先頭を一意に管理できるようになります。また、各ペアの処理では次の順序でポインタを張り替えています。

1. second の次のノードを temp として退避させる
2. first の next を second の次に向けて、first をペアの後ろに移動させる
3. second の next を first に向けて、second をペアの先頭にする
4. 前のペアの末尾（prev）の next を second につなぎ直して、リスト全体を連結する

この手法により、ノードの値を一切書き換えることなく、ポインタの付け替えだけで隣接ノードのペア交換を実現できます。計算量はリストの長さを n とすると O(n)、追加のメモリ使用量は O(1) です。