C++でのリンクリストのフラット化

この問題では、右と下の2つのポインタノードで構成されるリンクリストが表示されます。

• 右ノード はメインのリンクリストポインタです。

• ダウンノード そのノードで始まるセカンダリリンクリスト用です。

リンクリストはすべて並べ替えられています。

私たちのタスクは、リンクリストをフラット化するプログラムを作成することであり、結果のリスト自体がソートされたリストになります。

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

入力

出力

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

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

この問題の解決策は、リンクリストのマージソートを使用することです。 。このメソッドは、リストをソートされた順序で再帰的にマージして、フラット化されたリストを形成します。

例

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

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

class Node{
   public:
   int data;
   Node *right, *down;
};
Node* head = NULL;
Node* mergeList(Node* a, Node* b){
   if (a == NULL)
      return b;
   if (b == NULL)
      return a;
   Node* result;
   if (a->data < b->data){
      result = a;
      result->down = mergeList(a->down, b);
   }
   else{
      result = b;
      result->down = mergeList(a, b->down);
   }
   result->right = NULL;
   return result;
}
Node* flattenLinkedList(Node* root){
   if (root == NULL || root->right == NULL)
      return root;
   root->right = flattenLinkedList(root->right);
   root = mergeList(root, root->right);
   return root;
}
Node* push(Node* head_ref, int data){
   Node* new_node = new Node();
   new_node->data = data;
   new_node->right = NULL;
   new_node->down = head_ref;
   head_ref = new_node;
   return head_ref;
}
int main(){
   head = push(head, 7);
   head = push(head, 1);
   head->right = push(head->right, 11);
   head->right = push(head->right, 5);
   head->right = push(head->right, 4);
   head->right->right = push(head->right->right, 12);
   head->right->right = push(head->right->right, 6);
   head->right->right->right = push(head->right->right->right, 8);
   head->right->right->right->right = push(head->right->right->right->right, 16);
   head = flattenLinkedList(head);
   cout<<"The Flattened Linked list is : \n";
   Node* temp = head;
   while (temp != NULL){
      cout<<temp->data<<" => ";
      temp = temp->down;
   }
   cout<<"NULL";
   return 0;
}

出力

The Flattened Linked list is :
1 => 4 => 5 => 6 => 7 => 8 => 11 => 12 => 16 => NULL