C++에서 다단계 연결 목록 병합

이 문제에서는 다단계 연결 목록이 제공됩니다. 우리의 임무는 다단계 연결 목록을 평면화하는 프로그램을 만드는 것입니다.

병합 작업은 연결 목록에서 첫 번째 수준 노드가 먼저 발생하고 두 번째 수준 노드가 발생하는 방식으로 수행됩니다.

다단계 연결 목록 링크드 리스트의 모든 노드가 두 개의 링크 포인터를 가지는 다차원 데이터 구조, 하나는 다음 노드에 대한 링크이고 다른 하나는 하나 이상의 노드가 있는 자식 리스트에 대한 링크입니다. 이 자식 포인터는 다른 목록 노드를 가리킬 수도 있고 가리지 않을 수도 있습니다.

예시

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

입력

출력

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