C++で連結リストを奇数・偶数インデックスごとに分離する方法

連結リストとは

連結リスト(Linked List)は線形データ構造の一種で、各ノードが2つの部分で構成されています。片方にはノードの値(データ)が格納され、もう片方には次のノードへのアドレス(ポインタ)が格納されます。

ここでは、各ノードがデータと次ノードへのポインタを持つ連結リストを想定します。課題は、与えられた連結リストを「分離」することです。分離とは、リスト内の奇数番目(奇数インデックス)のノードと偶数番目(偶数インデックス)のノードを、それぞれまとめて分けることを意味します。

この問題を解くアプローチ

連結リストを分離するには、「奇数インデックス用」「偶数インデックス用」「偶数インデックスの先頭用」の3つのポインタを用意します。その後、連結リスト全体を走査しながら、各ポインタを適切な値で更新していきます。

連結リストのインデックスは「1」から始まるため、リストの最初のノードは常に奇数インデックスのノードとして扱われ、その次のノードは偶数インデックスのノードとして扱われます。

• データと次ノードへのポインタを持つ連結リストを用意します。
• 関数 segregateList(listnode *head) はヘッドノードへのポインタを受け取り、分離後の連結リストを出力として返します。
• 3つのポインタ oddIndex、evenIndex、evenHead を初期化し、まずリストの先頭を指すようにします。
• リスト全体を走査し、oddIndex の next ポインタに evenIndex の next ポインタを設定します。
• 続けてリスト全体を走査し、evenIndex の next ポインタに oddIndex の next ポインタを設定します。
• 最後にヘッドポインタを返します。

実装例

#include <iostream>
using namespace std;
class node {
    public:
        int data;
    node *next;
    node(int d) {
        data = d;
        next = NULL;
    }
};
node * segregateList(node * head) {
    if (head == NULL) {
        return NULL;
    }
    node * oddIndex = head;
    node * evenIndex = head -> next;
    node * evenHead = evenIndex;
    while (evenIndex != NULL and evenIndex -> next != NULL) {
        oddIndex -> next = evenIndex -> next;
        oddIndex = oddIndex -> next;
        evenIndex -> next = oddIndex -> next;
        evenIndex = evenIndex -> next;
    }
    oddIndex -> next = evenHead;
    return head;
}
void insertAtNode(node * & head, int data) {
    node * n = new node(data);
    n -> next = head;
    head = n;
}
void print(node * head) {
    while (head != NULL) {
        cout << head -> data << "->";
        head = head -> next;
    }
}
int main() {
    node * head = NULL;
    // 先頭ノードがNULL値を持つ場合もあり得ます。
    insertAtNode(head, 5);
    insertAtNode(head, 8);
    insertAtNode(head, 3);
    insertAtNode(head, 1);
    insertAtNode(head, 2);
    print(head);
    cout << endl;
    segregateList(head);
    print(head);
}

上記のコードを実行すると、次のような出力が得られます。

出力結果

2->3->5->1->8->

入力として与えた連結リストは 2->1->3->8->5-> です。インデックスで見ると、奇数番目のノードは「2、3、5」、偶数番目のノードは「1、8」となります。分離処理を行うことで、奇数インデックスのノードが前方に集められ、偶数インデックスのノードがその後に続く 2->3->5->1->8-> という結果が得られます。