C++で連結リストを指定した値を基準に分割し、元の順序を維持する方法

このチュートリアルでは、連結リストが与えられたとき、xより小さい数値をすべてリストの先頭側に集め、それ以外の数値を後ろ側に配置する方法を解説します。その際、各グループ内の要素の相対的な順序は元のまま維持しなければならない点がポイントです。

入力 : 1->4->3->2->5->2->3,
x = 3
出力 : 1->2->2->3->3->4->5

入力 : 1->4->2->10
x = 3
出力 : 1->2->4->10

入力 : 10->4->20->10->3
x = 3
出力 : 3->10->4->20->10

この問題を解くには、3つの連結リストを作成します。リストを走査している途中でxより小さい値を見つけたら1つ目のリストに挿入し、xと等しい値は2つ目のリストへ、xより大きい値は3つ目のリストへ振り分けていきます。最後にこれら3つのリストを連結し、完成したリストを出力すれば完了です。

解決アプローチ

このアプローチでは、「small（小さい）」「equal（等しい）」「large（大きい）」という3つのリストを管理します。各リスト内での要素の並び順を保持したまま、最後に3つのリストをこの順で連結したものが答えとなります。

実装例

上記アプローチのC++コード

#include<bits/stdc++.h>
using namespace std;
struct Node{ // ノード用の構造体
    int data;
    struct Node* next;
};
// 新しいノードを作成するユーティリティ関数
Node *newNode(int data){
    struct Node* new_node = new Node;
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}
struct Node *partition(struct Node *head, int x){
    struct Node *smallhead = NULL, *smalllast = NULL; // 各リストの先頭と末尾の
    // 2つのポインタを保持することで連結が容易になる
    struct Node *largelast = NULL, *largehead = NULL;
    struct Node *equalhead = NULL, *equallast = NULL;
    while (head != NULL){ // 元のリストを走査
        if (head->data == x){ // xと等しい値の場合
            if (equalhead == NULL)
                equalhead = equallast = head;
            else{
                equallast->next = head;
                equallast = equallast->next;
            }
        }
        else if (head->data < x){ // xより小さい値の場合
            if (smallhead == NULL)
                smalllast = smallhead = head;
            else{
                smalllast->next = head;
                smalllast = head;
            }
        }
        else{ // xより大きい値の場合
            if (largehead == NULL)
                largelast = largehead = head;
            else{
                largelast->next = head;
                largelast = head;
            }
        }
        head = head->next;
    }
    if (largelast != NULL) // 最後尾のリストなので末尾をNULLに設定
        largelast->next = NULL;
    /**********リストの連結**********/
    if (smallhead == NULL){
        if (equalhead == NULL)
            return largehead;
        equallast->next = largehead;
        return equalhead;
    }
    if (equalhead == NULL){
        smalllast->next = largehead;
        return smallhead;
    }
    smalllast->next = equalhead;
    equallast->next = largehead;
    return smallhead;
}
void printList(struct Node *head){ // リストを出力する関数
    struct Node *temp = head;
    while (temp != NULL){
        printf("%d ", temp->data);
        temp = temp->next;
    }
}
int main(){
    struct Node* head = newNode(10);
    head->next = newNode(4);
    head->next->next = newNode(5);
    head->next->next->next = newNode(30);
    head->next->next->next->next = newNode(2);
    head->next->next->next->next->next = newNode(50);
    int x = 3;
    head = partition(head, x);
    printList(head);
    return 0;
}

出力結果

2 10 4 5 30 50

コードの解説

上記のアプローチでは、要素を元の順序どおりに保持できるよう、3つの連結リストを利用します。それぞれのリストには、xより小さい要素、xと等しい要素、xより大きい要素が格納されます。これにより処理は非常にシンプルになり、あとは3つのリストを連結して先頭ノード（ヘッド）を返すだけで完了です。なお、計算量はリストを一度だけ走査するためO(n)、必要な追加領域はポインタ数個のみという効率的な実装になっています。

まとめ

このチュートリアルでは、連結リストを指定した値を基準に分割しながら元の順序を維持する問題を解きました。この問題に対するC++プログラムと、それを解くための標準的なアプローチについても学びました。同様のプログラムは、C、Java、Pythonなど他の言語でも実装可能です。このチュートリアルが皆さんのお役に立てば幸いです。