C++で連結リストをp:qの比率で2つのリストに分割する方法

このチュートリアルでは、与えられた連結リスト（リンクリスト）を p:q の比率で2つのリストに分割するC++プログラムを作成します。

アルゴリズム自体はシンプルです。まずは問題を解くための手順を確認しましょう。

解決手順

• 連結リストのノード用の構造体（struct）を定義します。
• ダミーデータを使って連結リストを初期化します。
• p:q の比率を設定します。
• 連結リスト全体の長さ（ノード数）を求めます。
• 連結リストの長さが p + q より小さい場合、その比率での分割は不可能なのでエラーを表示します。
• 可能な場合は、先頭から p 番目のノードまでポインタを進めます。
• p 番目のノードでリンクを切断し、その次のノードを2つ目の連結リストの新しいヘッドとして設定します。
• 最後に、分割された2つの連結リストを出力します。

サンプルコード

それでは、実際のコードを見てみましょう。

#include<bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    Node *next;
    Node(int data) {
        this->data = data;
        this->next = NULL;
    }
};
void printLinkedList(Node* head) {
    Node *temp = head;
    while (temp) {
        cout << temp->data << " -> ";
        temp = temp->next;
    }
    cout << "NULL" << endl;
}
void splitLinkedList(Node *head, int p, int q) {
    int n = 0;
    Node *temp = head;
    // 連結リストの長さを求める
    while (temp != NULL) {
        n += 1;
        temp = temp->next;
    }
    // 分割が可能かどうかをチェック
    if (p + q > n) {
        cout << "Can't divide Linked list" << endl;
    }
    else {
        temp = head;
        while (p > 1) {
            temp = temp->next;
            p -= 1;
        }
        // 分割後の2つ目のヘッドノード
        Node *head_two = temp->next;
        temp->next = NULL;
        // 連結リストを出力
        printLinkedList(head);
        printLinkedList(head_two);
    }
}
int main() {
    Node* head = new Node(1);
    head->next = new Node(2);
    head->next->next = new Node(3);
    head->next->next->next = new Node(4);
    head->next->next->next->next = new Node(5);
    head->next->next->next->next->next = new Node(6);
    int p = 2, q = 4;
    splitLinkedList(head, p, q);
}

実行結果

上記のコードを実行すると、以下の出力が得られます。

1 -> 2 -> NULL
3 -> 4 -> 5 -> 6 -> NULL

処理の流れのポイント

このアルゴリズムでは、まず連結リストを一度走査してノード総数 n を取得します。そのため時間計算量は O(n)、追加のメモリ使用量は O(1) となります。

また、p + q がノード総数より大きい場合には分割ができないため、事前にチェックを行って安全に処理を終了している点も重要です。

まとめ

本記事では、連結リストを指定した比率 p:q で2つのリストに分割するC++の実装方法を紹介しました。リンクの切断位置を正しく制御することがポイントです。

このチュートリアルについて質問がある場合は、ぜひコメント欄でお知らせください。