C++で連結リストをパーティション分割するアルゴリズム

問題の概要

連結リストと値 x が与えられたとき、リストを2つのグループに分割することを考えます。具体的には、「x 未満のノード」がすべて「x 以上のノード」よりも前に来るように並べ替えます。ただし、各グループ内ではノードの元の相対的な順序を保持しなければなりません。

例えば、リストが [1,4,3,2,5,2]、x = 3 の場合、出力は [1,2,2,4,3,5] となります。3未満のノード（1, 2, 2）が先頭に集まり、3以上のノード（4, 3, 5）がその後に続きます。

解法のアプローチ

この問題は、ダミーノードを2つ使うことでシンプルに解決できます。手順は以下の通りです。

• 初期値 -1 を持つダミーノード d1 と d2 を作成し、それぞれを指すポインタ dp1 と dp2 を用意します。
• 走査用のポインタ a が NULL でない間、以下を繰り返します。
  • a の値が b（= x）未満の場合：dp1 の next に新しいノードを接続し、dp1 を前進させます。
  • それ以外の場合：dp2 の next に新しいノードを接続し、dp2 を前進させます。
  • a を次のノードへ進めます。
• ループ終了後、dp1 の next に d2 の next をつなぎ、2つのリストを連結します。
• d1 の next を結果として返します。

この方法なら、元の順序を保ちながら一度の走査で分割が完了します。計算量は時間・空間ともに O(n) です。

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* partition(ListNode* a, int b) {
        ListNode* dummy1 = new ListNode(-1);
        ListNode* dummy2 = new ListNode(-1);
        ListNode* dummyPtr1 = dummy1;
        ListNode* dummyPtr2 = dummy2;
        while(a){
            if(a->val < b){
                dummyPtr1->next = new ListNode(a->val);
                dummyPtr1 = dummyPtr1->next;
            }
            else{
                dummyPtr2->next = new ListNode(a->val);
                dummyPtr2 = dummyPtr2->next;
            }
            a = a->next;
        }
        dummyPtr1->next = dummy2->next;
        return dummy1->next;
    }
};
main(){
    Solution ob;
    vector<int> v = {1,4,6,3,2,5,2,8};
    ListNode *head = make_list(v);
    print_list(ob.partition(head, 3));
}

入力

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

出力

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

まとめ

ダミーノードを活用したこの手法は、条件分岐しながら2つの新しいリストを構築し、最後にそれらを連結するだけという非常に直感的なアプローチです。特別なソート処理を行うことなく、安定した順序でリストを分割できるため、面接や競技プログラミングでも頻出のテクニックとなっています。