C++でマルチレベルリンクリストをフラット化する

この問題では、マルチレベルのリンクリストが提供されます。私たちの仕事は、マルチレベルのリンクリストをフラット化するプログラムを作成することです。

平坦化操作は、リンクリストで最初に第1レベルのノードが発生し、次に第2レベルのノードが発生するように実行されます。

マルチレベルリンクリスト は多次元データ構造であり、リンクリストのすべてのノードに2つのリンクポインタがあります。1つは次のノードへのリンクで、もう1つは1つ以上のノードを持つ子リストへのリンクです。この子ポインタは、他のリストノードを指している場合とそうでない場合があります。

例

問題を理解するために例を見てみましょう

入力

出力

1-> 9-> 8 -> 4 -> 6-> 7-> 2-> 3-> 5

ソリューションアプローチ

この問題の簡単な解決策は、アルゴリズムのレベルオーダートラバーサルタイプを使用することです。最初のノードから開始して、同じレベルのすべてのノードをトラバースするリンクリストをトラバースします。ノードに子ポインターが存在する場合は、テールポインターを使用して、ノードを現在のリンクリストの最後に移動します。次に、リンクリストの子ノードごとに同じトラバーサルを再帰的に実行します。以下のプログラムは、ロジックをより詳しく説明します。

例

ソリューションの動作を説明するプログラム

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

#define SIZE(arr) (sizeof(arr)/sizeof(arr[0]))

class Node{
   public:
   int data;
   Node *next;
   Node *child;
};
Node *createList(int *arr, int n){
   Node *head = NULL;
   Node *p;
   int i;
   for (i = 0; i < n; ++i){
      if (head == NULL)
         head = p = new Node();
      else{
         p->next = new Node();
         p = p->next;
      }
      p->data = arr[i];
      p->next = p->child = NULL;
   }
   return head;
}
Node *createList(void){
   int arr1[] = {1, 9, 8, 4, 6};
   int arr2[] = {7, 3, 2};
   int arr3[] = {5};
   Node *head1 = createList(arr1, (sizeof(arr1)/sizeof(arr1[0])));
   Node *head2 = createList(arr2, (sizeof(arr2)/sizeof(arr2[0])));
   Node *head3 = createList(arr3, (sizeof(arr3)/sizeof(arr3[0])));
   head1->child = head2;
   head1->next->child = head3;
   return head1;
}
void flattenLinkedList(Node *head){
   if (head == NULL)
   return;
   Node *tmp;
   Node *tail = head;
   while (tail->next != NULL)
   tail = tail->next;
   Node *cur = head;
   while (cur != tail){
      if (cur->child){
         tail->next = cur->child;
         tmp = cur->child;
         while (tmp->next)
         tmp = tmp->next;
         tail = tmp;
      }
      cur = cur->next;
   }
}
int main(void){
   Node *head = NULL;
   head = createList();
   flattenLinkedList(head);
   cout<<"The flattened Linked List is ";
   while (head != NULL){
      cout << head->data << " ";
      head = head->next;
   }
   return 0;
}

出力

The flattened Linked List is 1 9 8 4 6 7 3 2 5