C++で連結リストを並べ替える方法：リオーダーアルゴリズムの実装

問題の概要

次のような連結リストを考えます。
l1 → l2 → l3 → l4 → … → l(n-1) → ln
これを、以下の形式になるように並べ替えます。
l1 → ln → l2 → l(n-1) → …

ここでの重要な制約は、リストノードが保持している値を変更してはならないという点です。並べ替えはノード同士のつながり（next ポインタ）の付け替えだけで行う必要があります。

例えば、リストが [1,2,3,4,5] である場合、出力は [1,5,2,4,3] となります。

解法の考え方

この問題は「中央を見つける」「後半を反転する」「2つのリストを交互につなぐ」という3つのフェーズに分けて考えると分かりやすくなります。具体的には以下の手順で進めます。

ステップ1：リストを反転する reverse メソッドを定義

先頭ノード head と前のノード prev を引数に取る reverse メソッドを作成し、以下のように動作させます。

• head が NULL の場合は prev を返す（再帰の終了条件）
• 一時変数 temp に head の次のノードを保存する
• head の next を prev に向け直し、prev を head に更新する
• reverse(temp, prev) を再帰的に呼び出して結果を返す

ステップ2：リストを並べ替える reorder 処理

• head が NULL の場合は NULL を返す
• slow と fast という2つのノードポインタを用意し、どちらも head で初期化する（いわゆる「ウサギとカメ」のテクニックです）
• fast および fast の次のノードがどちらも NULL でない間、slow を1つ、fast を2つずつ進めます
• ループ終了時、slow はリストのほぼ中央に到達しています
• fast = reverse(slow->next) として、リストの後半部分を反転します
• slow->next を NULL に設定して前半と後半を切り離し、slow を head に戻します
• 作業用のリストノードポインタ temp1 と temp2 を宣言します
• fast が NULL になるまで、以下を繰り返して前半と後半を交互に結合します
  • temp1 に slow の次のノードを、temp2 に fast の次のノードを保存する
  • slow の next を fast に、fast の next を temp1 に設定して交差させる
  • slow を temp1 へ、fast を temp2 へ進める

動作の流れ（[1,2,3,4,5] の場合）

• 中央探索後：前半 [1,2,3] ／ 後半 [4,5]
• 後半を反転：[5,4]
• 交互に結合：1 → 5 → 2 → 4 → 3

計算量について補足すると、リストの長さを N としたとき時間計算量は O(N) です。空間計算量は、反転を再帰で行っているため O(N) となり、反転を反復処理に置き換えれば O(1) に抑えられます。

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){
        cout << ptr->val << ", ";
        ptr = ptr->next;
    }
    cout << "]" << endl;
}
class Solution {
    public:
    ListNode* successor = NULL;
    ListNode* reverse(ListNode* head, ListNode* prev = NULL){
        if(!head)return prev;
        ListNode* temp = head->next;
        head->next = prev;
        prev = head;
        return reverse(temp, prev);
    }
    void reorderList(ListNode* head) {
        if(!head)return;
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = reverse(slow->next);
        slow->next = NULL;
        slow = head;
        ListNode *temp1, *temp2;
        while(fast){
            temp1 = slow->next;
            temp2 = fast->next;
            slow->next = fast;
            fast->next = temp1;
            slow = temp1;
            fast = temp2;
        }
    }
};
main(){
    vector<int> v = {1,2,3,4,5};
    ListNode *h1 = make_list(v);
    Solution ob;
    (ob.reorderList(h1));
    print_list(h1);
}

入力

[1,2,3,4,5]

出力

[1, 5, 2, 4, 3]

このコードでは、make_list 関数でベクトルから連結リストを構築し、reorderList メソッドで並べ替えを実行した後、print_list 関数で結果を出力しています。入力 [1,2,3,4,5] が [1,5,2,4,3] と正しく並べ替えられていることが確認できます。