C++で連結リストの各ノードの右側にある最大値ノードを任意ポインタに設定する方法

この記事では、値(data)、次ノードへのポインタ(next)、さらに任意ポインタ(arbitrary)を持つ連結リストが与えられたとき、各ノードの任意ポインタを「そのノードより右側に存在する最大値のノード」に向けるアルゴリズムについて解説します。

問題の概要

連結リストの各ノードには通常のnextポインタに加えて、もう一つのポインタ(任意ポインタ)があります。この任意ポインタを、自分より右側にあるノードの中で値が最大のものを指すように書き換えるのが今回のタスクです。

以下の例で問題を理解しましょう。

図のように、各ノードの任意ポインタは、その右側に存在する最大の要素を指しています。

12 -> 76, 76 -> 54, 54 -> 8, 8 -> 41

解決アプローチ:逆順トラバーサル

この問題を解く鍵は、「各ノードの右側にある最大要素」を効率よく求めることです。各ノードごとに右側をすべて調べる方法だとO(n²)かかりますが、連結リストを逆順に走査すれば、一度の走査(O(n))で解決できます。

具体的な手順は以下の通りです。

1. まず連結リスト全体を反転します。
2. 反転後の先頭ノード(元のリストの末尾ノード)を「現時点での最大ノード」として保持します。
3. 残りのノードを順に走査し、各ノードの任意ポインタを現在の最大ノードに設定します。
4. 走査中に現在の最大値より大きな値を持つノードが出てきたら、最大ノードを更新します。
5. すべての処理が終わったら、再度リストを反転して元の順序に戻します。

この方法なら、時間計算量はO(n)、追加の空間計算量はO(1)と非常に効率的です。

C++での実装例

上記のアイデアを実装したプログラムがこちらです。

#include<bits/stdc++.h>
using namespace std;

struct Node{
    int data;
    Node* next, *arbitrary;
};

// 連結リストを反転する関数
Node* reverseList(Node *head){
    Node *prev = NULL, *current = head, *next;
    while (current != NULL){
        next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    return prev;
}

// 任意ポインタを設定する関数
Node* populateArbitraray(Node *head){
    head = reverseList(head);   // リストを反転
    Node *max = head;           // 現時点での最大ノード
    Node *temp = head->next;
    while (temp != NULL){
        temp->arbitrary = max;          // 最大ノードを任意ポインタに設定
        if (max->data < temp->data)
            max = temp;                 // より大きい値なら最大ノードを更新
        temp = temp->next;
    }
    return reverseList(head);   // 再度反転して元の順序に戻す
}

// 新しいノードを作成する関数
Node *insertNode(int data) {
    Node *new_node = new Node;
    new_node->data = data;
    new_node->next = NULL;
    return new_node;
}

int main() {
    Node *head = insertNode(12);
    head->next = insertNode(76);
    head->next->next = insertNode(54);
    head->next->next->next = insertNode(8);
    head->next->next->next->next = insertNode(41);

    head = populateArbitraray(head);

    printf("Linked List with Arbitrary Pointer: \n");
    while (head!=NULL){
        cout<<head->data<<"->";
        if (head->next)
            cout<<head->next->data;
        else
            cout<<"NULL";
        cout<<": "<<head->data<<"->";
        if (head->arbitrary)
            cout<<head->arbitrary->data;
        else
            cout<<"NULL";
        cout << endl;
        head = head->next;
    }
    return 0;
}

出力結果

Linked List with Arbitrary Pointer:
12->76: 12->76
76->54: 76->54
54->8: 54->41
8->41: 8->41
41->NULL: 41->NULL

出力の各行は「ノードの値->次ノードの値 : ノードの値->任意ポインタが指すノードの値」を表しています。たとえば「54->8: 54->41」は、ノード54の任意ポインタが、その右側で最大値となるノード41を指していることを示します。末尾ノード41の右側にはノードが存在しないため、任意ポインタはNULLのままです。

まとめ

連結リストを一度反転してから走査することで、各ノードの右側にある最大値ノードを任意ポインタに設定できました。時間計算量O(n)・空間計算量O(1)と効率的な手法です。なお、実務では変数名 max が標準ライブラリの std::max と紛らわしいので、maxNode のような名前に変更しておくと可読性が上がります。「右側の最大値」を求める問題は配列でも頻出のテーマなので、この逆順トラバーサルのテクニックはぜひ覚えておきましょう。