C++の任意ポインタ（arbitrary pointer）を使って連結リスト内の次に大きい値のノードを指す方法

この問題では、「値（data）」「nextポインタ」「任意ポインタ（arbit）」の3つの要素を持つ連結リストが与えられます。求められているのは、各ノードの任意ポインタが、リスト内でそのノードより大きい値の中で最も近いもの（＝次に大きい値）を指すようにすることです。

問題の例

例を見て理解しましょう。

たとえば、8 → 12 → 41 → 54 → 76 のように、各ノードの任意ポインタが「自分より大きい次の要素」を順に指すようになります。つまり、8は12を、12は41を、41は54を、54は76を指します。

解決アプローチ：マージソートを活用する

この問題を効率的に解くには、マージソート（merge sort）のアルゴリズムを利用します。

ポイントは、通常のnextポインタではなく任意ポインタ（arbit）を主ポインタとして扱い、そのポインタ列に対してマージソートを行うことです。ソートが完了すると、任意ポインタの並びが昇順になるため、結果として各任意ポインタは自動的に「次に大きいノード」を指すことになります。

アルゴリズムの手順

1. すべてのノードの任意ポインタを、一旦nextポインタと同じ参照に設定します。
2. 任意ポインタを基準にして連結リストをマージソートします。
3. ソート後の任意ポインタの順序が、そのまま「次に大きい値へのポインタ」となります。

C++での実装例

以下は、この解法を実装したC++プログラムです。

#include <iostream>
using namespace std;
class Node {
   public:
   int data;
   Node* next, *arbit;
};
Node* SortedMerge(Node* a, Node* b);
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef);

// 任意ポインタを基準にマージソートを実行
void MergeSort(Node** headRef) {
   Node* head = *headRef;
   Node* a, *b;
   if ((head == NULL) || (head->arbit == NULL))
      return;
   FrontBackSplit(head, &a, &b);
   MergeSort(&a);
   MergeSort(&b);
   *headRef = SortedMerge(a, b);
}

// ソート済みの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->arbit = SortedMerge(a->arbit, b);
   } else {
      result = b;
      result->arbit = SortedMerge(a, b->arbit);
   }
   return (result);
}

// リストを前半と後半に分割（フロイドの高速・低速ポインタ法）
void FrontBackSplit(Node* source, Node** frontRef, Node** backRef) {
   Node* fast, *slow;
   if (source == NULL || source->arbit == NULL){
      *frontRef = source;
      *backRef = NULL;
      return;
   }
   slow = source, fast = source->arbit;
   while (fast != NULL){
      fast = fast->arbit;
      if (fast != NULL){
         slow = slow->arbit;
         fast = fast->arbit;
      }
   }
   *frontRef = source;
   *backRef = slow->arbit;
   slow->arbit = NULL;
}

// 先頭に新しいノードを追加
void addNode(Node** head_ref, int new_data) {
   Node* new_node = new Node();
   new_node->data = new_data;
   new_node->next = (*head_ref);
   new_node->arbit = NULL;
   (*head_ref) = new_node;
}

// 任意ポインタを設定し、マージソートを適用
Node* populateArbitraray(Node *head) {
   Node *temp = head;
   while (temp != NULL){
      temp->arbit = temp->next;
      temp = temp->next;
   }
   MergeSort(&head);
   return head;
}

int main() {
   Node* head = NULL;
   addNode(&head, 45);
   addNode(&head, 12);
   addNode(&head, 87);
   addNode(&head, 32);
   Node *ahead = populateArbitraray(head);
   cout << "\t\tArbitrary pointer overlaoded \n Traversing linked List\n";
   cout<<"Using Next Pointer\n";
   while (head!=NULL){
      cout << head->data << ", ";
      head = head->next;
   }
   printf("\nUsing Arbit Pointer\n");
   while (ahead!=NULL){
      cout<<ahead->data<<", ";
      ahead = ahead->arbit;
   }
   return 0;
}

実行結果

Arbitrary pointer overlaoded
Traversing linked List
Using Next Pointer
32, 87, 12, 45,
Using Arbit Pointer
12, 32, 45, 87,

解説のまとめ

実行結果からわかるように、nextポインタで辿ると元の順序（32, 87, 12, 45）ですが、任意ポインタで辿ると昇順（12, 32, 45, 87）になっています。これは、任意ポインタが各ノードの「次に大きい値」を正しく指していることを意味します。

この手法の計算量は、マージソートに基づいているため O(n log n) であり、各ノードの任意ポインタを個別に計算する素朴な O(n²) の方法よりも効率的です。また、分割処理にはフロイドの高速・低速ポインタ法を用いることで、リスト中央の検出も効率的に行っています。