C++でリンクリストを交互にソートする方法（最小値・最大値の交互並び替え）

リンクリスト（連結リスト）は、要素そのものに加えて次のノードへのポインタも保持する線形データ構造です。

本記事で扱う「交互ソート（alternate sort）」とは、リンクリストを以下のような順序で並べ替えることを指します。1番目のノードには最小値、2番目のノードには最大値、3番目のノードには2番目に小さい値、4番目のノードには2番目に大きい値……というように、最小値と最大値を交互に配置していきます。

問題の例

具体例を見てみましょう。

入力 : 3 > 4 > 21 > 67 > 1 > 8
出力 : 1 > 67 > 3 > 21 > 4 > 8

要素を昇順に並べると「1, 3, 4, 8, 21, 67」です。求められる出力は、このソート済み列の先頭から1つ、末尾から1つと交互に値を取り出して構成します。つまり「1（最小）→ 67（最大）→ 3（2番目に小さい）→ 21（2番目に大きい）→ 4 → 8」という並びになります。

解決のアプローチ

最小値と最大値を交互に並べる必要があるため、まずリンクリスト全体を昇順にソートするのが自然な方針です。ソートには任意のアルゴリズムを使えますが、リンクリストに対してはマージソートが効率的で、後述の手順でもマージ処理を利用するため相性が良いです。

ソート後のリストを前半と後半の2つのリストに分割し、後半を反転させます。こうすると、前半は小さい値の昇順、反転した後半は大きい値の降順になります。あとはこの2つのリストを交互にマージすれば、目的の並びが完成します。2つの独立したリストとして扱うことで、要素の重複やポインタの混在を防げる点もポイントです。

アルゴリズム

1. リンクリストをマージソートで昇順にソートする。
2. 元のリストを長さ半分ずつの2つのリンクリストに分割する（前半リストと後半リスト）。
3. 後半のリンクリストを反転し、新しいリンクリストとして保持する。
4. 前半リストと反転済みリストの要素を交互に使って、結果となるリンクリストを構築する。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
Node* getNode(int data){
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef) ;
Node* SortedMerge(Node* a, Node* b) ;
void MergeSort(Node** headRef) ;
void alternateMerge(Node* head1, Node* head2) ;
Node* altSortLinkedList(Node* head) ;
void printList(Node* head) ;
// リストを反転する関数
static void reverse(Node** head_ref){
    Node* prev = NULL;
    Node* current = *head_ref;
    Node* next;
    while (current != NULL) {
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    *head_ref = prev;
}
int main(){
    Node* head = getNode(3);
    head->next = getNode(4);
    head->next->next = getNode(21);
    head->next->next->next = getNode(67);
    head->next->next->next->next = getNode(1);
    head->next->next->next->next->next = getNode(8);
    cout << "Initial list: ";
    printList(head);
    head = altSortLinkedList(head);
    cout << "\nSorted list: ";
    printList(head);
    return 0;
}
// 高速・低速ポインタを使ってリストを前半と後半に分割
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef){
    Node* fast;
    Node* slow;
    if (source == NULL || source->next == NULL) {
        *frontRef = source;
        *backRef = NULL;
    }
    else {
        slow = source;
        fast = source->next;
        while (fast != NULL) {
            fast = fast->next;
            if (fast != NULL) {
                slow = slow->next;
                fast = fast->next;
            }
        }
        *frontRef = source;
        *backRef = slow->next;
        slow->next = NULL;
    }
}
// ソート済み2つのリストをマージ
Node* SortedMerge(Node* a, Node* b){
    Node* result = NULL;
    if (a == NULL)
        return b;
    else if (b == NULL)
        return a;
    if (a->data <= b->data) {
        result = a;
        result->next = SortedMerge(a->next, b);
    } else {
        result = b;
        result->next = SortedMerge(a, b->next);
    }
    return result;
}
// マージソート本体
void MergeSort(Node** headRef){
    Node* head = *headRef;
    Node *a, *b;
    if ((head == NULL) || (head->next == NULL))
        return;
    FrontBackSplit(head, &a, &b);
    MergeSort(&a);
    MergeSort(&b);
    *headRef = SortedMerge(a, b);
}
// 2つのリストの要素を交互につなぎ合わせる
void alternateMerge(Node* head1, Node* head2){
    Node *p, *q;
    while (head1 != NULL && head2 != NULL) {
        p = head1->next;
        head1->next = head2;
        head1 = p;
        q = head2->next;
        head2->next = head1;
        head2 = q;
    }
}
// 交互ソートのメイン処理
Node* altSortLinkedList(Node* head){
    MergeSort(&head);
    Node *front, *back;
    FrontBackSplit(head, &front, &back);
    reverse(&back);
    alternateMerge(front, back);
    return front;
}
void printList(Node* head){
    while (head != NULL) {
        cout << head->data << " ";
        head = head->next;
    }
}

実行結果

Initial list: 3 4 21 67 1 8
Sorted list: 1 67 3 21 4 8

計算量について

この手法の時間計算量は、マージソートの計算量に支配されるため O(n log n) となります。リストの分割・反転・交互マージはいずれも線形時間 O(n) で完了するため、全体として効率的な実装と言えます。また、ノードの付け替えだけで処理を行っているため、追加のメモリ消費も最小限に抑えられます。