C++で単方向連結リストを奇数・偶数が交互に並ぶよう並べ替える方法

単方向連結リスト(シングルリンクリスト)は、「データ」と「次の要素へのポインタ」の2つの部分から構成される線形データ構造です。

奇数・偶数が交互に並ぶ連結リストとは?

奇数・偶数交互連結リストとは、あるノードのデータが偶数であれば、その隣のノードのデータは奇数になるように並んだ連結リストのことを指します。

本記事では、既存の単方向連結リストを、以下のいずれかの形式に並べ替える問題を扱います。

• 先頭が偶数の場合:1番目が偶数、2番目が奇数、3番目が偶数…という順序で並べる
• 先頭が奇数の場合:1番目が奇数、2番目が偶数、3番目が奇数…という順序で並べる

具体例で理解しよう

例として、次の連結リストを考えてみます。

45 → 21 → 2 → 213 → 3 → 34 → 78 → 12

このリストを並べ替えると、結果は次のようになります。

45 → 2 → 21 → 34 → 213 → 78 → 3 → 12

このリストには偶数(2, 34, 78, 12)と奇数(45, 21, 213, 3)が混在しています。並べ替えでは、偶数を偶数番目の位置へ、奇数を奇数番目の位置へ配置することで、交互の並びを実現します。

スタックを使った解法の考え方

この種の問題には複数の解法がありますが、ここでは最もシンプルなスタックを利用する方法を紹介します。基本的な発想は次のとおりです。

1. 偶数用と奇数用の2つのスタックを用意します。
2. 連結リストを走査し、「本来あるべき位置と異なる」ノードを見つけたら、対応するスタックにプッシュします。具体的には、偶数位置に存在する奇数ノードは奇数スタックへ、奇数位置に存在する偶数ノードは偶数スタックへ格納します。
3. 走査が終わったら、両スタックから交互にノードを取り出して値を入れ替えます。スタックが空になった時点で、目的の連結リストが完成します。
4. 最後に連結リストの要素を出力します。

アルゴリズム

ステップ1 : 連結リスト内の順序が崩れた偶数ノード・奇数ノードを保持するためのスタックを作成する。
ステップ2 : 連結リストを走査しながら以下を実行する。
    ステップ2.1 : 奇数ノードが誤った位置(偶数位置)にある場合、奇数スタックにプッシュする。
    ステップ2.2 : 偶数ノードが誤った位置(奇数位置)にある場合、偶数スタックにプッシュする。
ステップ3 : スタックから交互に要素を取り出して入れ替える。スタックが空になった時点で、必要な連結リストが得られる。
ステップ4 : 連結リストの要素を出力する。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node* next;
};
void printList(struct Node* node);
Node* newNode(int key){
    Node* temp = new Node;
    temp->data = key;
    temp->next = NULL;
    return temp;
}
Node* insertBeg(Node* head, int val){
    Node* temp = newNode(val);
    temp->next = head;
    head = temp;
    return head;
}
void OddEvenList(Node* head);
int main(){
    Node* head = newNode(45);
    head = insertBeg(head, 21);
    head = insertBeg(head, 2);
    head = insertBeg(head, 213);
    head = insertBeg(head, 3);
    head = insertBeg(head, 34);
    head = insertBeg(head, 78);
    head = insertBeg(head, 12);
    cout << "Linked List:" << endl;
    printList(head);
    OddEvenList(head);
    cout << "Linked List after "
    << "Rearranging:" << endl;
    printList(head);
    return 0;
}
void printList(struct Node* node){
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}
void OddEvenList(Node* head){
    stack<Node*> odd;
    stack<Node*> even;
    int i = 1;
    while (head != nullptr) {
        if (head->data % 2 != 0 && i % 2 == 0) {
            odd.push(head);
        }
        else if (head->data % 2 == 0 && i % 2 != 0) {
            even.push(head);
        }
        head = head->next;
        i++;
    }
    while (!odd.empty() && !even.empty()) {
        swap(odd.top()->data, even.top()->data);
        odd.pop();
        even.pop();
    }
}

出力結果

Linked List:
12 78 34 3 213 2 21 45
Linked List after Rearranging:
3 78 45 12 213 2 21 34

計算量について

このアルゴリズムでは、連結リストを一度走査するため、時間計算量は O(n) となります。また、誤った位置にあるノードのアドレスを最大 n/2 個までスタックに保持するため、空間計算量も O(n) です。ノードのつながり(ポインタ)を変更せず、データの値だけを入れ替えている点もこの実装の特徴です。