C++에서 연결 목록 병합

이 문제에서는 오른쪽과 아래쪽의 두 포인터 노드로 구성된 연결 목록이 제공됩니다.

• 오른쪽 노드 주요 연결 목록 포인터입니다.

• 다운 노드 해당 노드로 시작하는 보조 연결 목록용입니다.

모든 연결 목록이 정렬됩니다.

우리의 임무는 연결 목록을 평면화하는 프로그램을 만드는 것이며 결과 목록 자체는 정렬된 목록이 될 것입니다.

문제를 이해하기 위해 예를 들어보겠습니다.

입력

출력

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