C++で双方向リンクリストの誤ったポインタを検出して修正する方法

このチュートリアルでは、双方向リンクリスト（doubly linked list）のランダムポインタを修正するプログラムについて解説します。

ここでは、双方向リンクリストのうち1つのノードが誤ったポインタ（prevポインタ）を持っている状況を想定します。私たちのタスクは、ポインタが本来指すべき要素（隣接するノード）を正しく指すように修正することです。

アプローチ

リストを先頭から順に走査し、各ノードについて以下の整合性を確認します。

• 現在のノードの next ノードの prev ポインタが、現在のノード自身を指しているか
• 現在のノードの prev ノードの next ポインタが、現在のノード自身を指しているか

不整合が見つかった時点で、そのポインタを正しいノードに付け替えて処理を終了します。これにより、最小限の走査で壊れたリンクを修復できます。

例（C++コード）

#include <bits/stdc++.h>
using namespace std;
// 双方向リンクリストのノード構造体
struct node {
   int data;
   node* next;
   node* prev;
};
// 新しいノードの作成
node* newNode(int data){
   node* temp = new node;
   temp->data = data;
   temp->next = temp->prev = NULL;
   return temp;
}
// 誤ったポインタの修正
void get_cpointer(node*& head){
   if (!head)
      return;
   node* temp = head;
   if (head->next && head->next->prev != head) {
      head->next->prev = head;
      return;
   }
   // 位置が正しくない場合は修正する
   if (head->prev != NULL) {
      head->prev = NULL;
      return;
   }
   temp = temp->next;
   while (temp) {
      if (temp->next && temp->next->prev != temp) {
         temp->next->prev = temp;
         return;
      }
      else if (temp->prev && temp->prev->next != temp) {
         temp->prev->next = temp;
         return;
      }
      temp = temp->next;
   }
}
// 双方向リンクリストの表示
void printList(node* head) {
   node* temp = head;
   while (temp) {
      cout << temp->data << " (";
      cout << (temp->prev ? temp->prev->data : -1)<< ") ";
      temp = temp->next;
   }
   cout << endl;
}
int main(){
   node* head = newNode(1);
   head->next = newNode(2);
   head->next->prev = head;
   head->next->next = newNode(3);
   head->next->next->prev = head;
   head->next->next->next = newNode(4);
   head->next->next->next->prev = head->next->next;
   cout << "\nIncorrect Linked List: ";
   printList(head);
   get_cpointer(head);
   cout << "\nCorrected Linked List: ";
   printList(head);
   return 0;
}

出力

Incorrect Linked List: 1 (-1) 2 (1) 3 (1) 4 (3)
Corrected Linked List: 1 (-1) 2 (1) 3 (2) 4 (3)

コードの解説

main 関数では、ノード3の prev ポインタが誤ってノード1を指すようにリストを意図的に構築しています。printList 関数は、各ノードのデータと、その prev ポインタが指すノードの値（存在しない場合は -1）を出力します。

get_cpointer 関数を実行すると、ノード3の prev ポインタが正しくノード2を指すように修正され、出力結果からもリスト全体の整合性が復元されたことが確認できます。

このアルゴリズムの計算量は O(n) であり、リストを1回走査するだけで済むため、効率的に誤ったリンクを検出・修正できるのが特徴です。