ÇOK DÜZEYLI BAĞLANTILI LISTEYI DÜZLEŞTIRIN (DERINLIK AÇISINDAN)

Bağlantılı bir liste verildiğinde, bunlara ek olarak Sonraki Her düğümün bir işaretçisi vardır çocuk Ayrı bir listeye işaret eden veya etmeyen işaretçi. Bu çocuk listelerinde şunlar olabilir: bir veya daha fazla kendi çocuklarını üretmek için çok düzeyli bağlantılı liste. Verilen KAFA arasında birinci seviye listenin. Görev, düzleştirmek tüm düğümlerin bir arada görünmesi için liste tek seviyeli bağlantılı liste. Listeyi, tüm düğümlerin aynı hizada olacağı şekilde düzleştirin. birinci seviye gelmeli Birinci daha sonra düğümlerin ikinci seviye vb.

Örnekler:

Giriş:

Çıkış: 1->4->6->2->5->7->3->8
Açıklama: Çok düzeyli bağlantılı liste, alt işaretçileri olmadığından düzleştirilmiştir.

tartıştık çok düzeyli bağlantılı listenin düzleştirilmesi düğümlerin iki aşağı ve sonraki işaretçisi olduğu yer. Bir önceki yazımızda düzleştirilmiş bağlantılı liste seviye açısından. Bağlantılı listeyi her zaman işlememiz gerektiğinde nasıl düzleştiririz? aşağı işaretçi her düğümde önce sonraki.

İçerik Tablosu

[Beklenen Yaklaşım] Özyinelemeyi Kullanma - O(n) Zaman ve O(n) Uzay
[Alternatif Yaklaşım] Yığın Kullanımı - O(n) Zaman ve O(n) Uzay

[Beklenen Yaklaşım] Özyinelemeyi Kullanma - O(n) Zaman ve O(n) Uzay

Yaklaşım şu şekildedir: yinelemeli olarak düzleştirmek çok seviyeli bağlantılı Her düğümü ve alt düğümlerini geçerek listeleyin. Birinci çocuk listesini düzleştir yinelemeyi kullanarak. Çocuk listesi düzleştirildikten sonra şuraya ilerleyin: sonraki düğüm sırayla. Geçiş sırasında bir referans -e daha önce ziyaret edilen düğüm ve onu mevcut düğüme bağlayın. Bu süreç, farklı seviyelerdeki tüm düğümlerin tek bir ağda birbirine bağlanmasını sağlar. tek doğrusal liste korurken derinlik açısından düzen.

karakterden tam sayıya java

C++

// A C++ program to flatten a multi- // linked list depth-wise #include    using namespace std; class Node {  public:  int data;  Node *next;  Node *down;  Node(int x) {  data = x;  next = down = nullptr;  } }; void flattenList(Node *curr Node *&prev) {  if (curr == nullptr)  return;  // Add the current element to the list.  if (prev != nullptr)  prev->next = curr;  prev = curr;  // Store the next pointer  Node *next = curr->next;  // Recursively add the bottom list  flattenList(curr->down prev);  // Recursively add the next list  flattenList(next prev); } void printList(Node *head) {  Node *curr = head;  while (curr != nullptr) {  cout << curr->data << ' ';  curr = curr->next;  }  cout << endl; } int main() {  // Create a hard coded multi-linked list.  // 5 -> 10 -> 19 -> 28  // | |  // 7 22  // | |  // 8 50  // |  // 30  Node *head = new Node(5);  head->down = new Node(7);  head->down->down = new Node(8);  head->down->down->down = new Node(30);  head->next = new Node(10);  head->next->next = new Node(19);  head->next->next->down = new Node(22);  head->next->next->down->down = new Node(50);  head->next->next->next = new Node(28);  Node *prev = nullptr;  flattenList(head prev);  printList(head);  return 0; }

Java

// A Java program to flatten a multi- // linked list depth-wise class Node {  int data;  Node next down;  Node(int x) {  data = x;  next = down = null;  } } class GfG {    static void flattenList(Node curr Node[] prev) {  if (curr == null)  return;  // Add the current element to the list.  if (prev[0] != null)  prev[0].next = curr;  prev[0] = curr;  // Store the next pointer  Node next = curr.next;  // Recursively add the bottom list  flattenList(curr.down prev);  // Recursively add the next list  flattenList(next prev);  }  static void printList(Node head) {  Node curr = head;  while (curr != null) {  System.out.print(curr.data + ' ');  curr = curr.next;  }  System.out.println();  }  public static void main(String[] args) {    // Create a hard coded multi-linked list.  // 5 -> 10 -> 19 -> 28  // | |  // 7 22  // | |  // 8 50  // |  // 30  Node head = new Node(5);  head.down = new Node(7);  head.down.down = new Node(8);  head.down.down.down = new Node(30);  head.next = new Node(10);  head.next.next = new Node(19);  head.next.next.down = new Node(22);  head.next.next.down.down = new Node(50);  head.next.next.next = new Node(28);  Node[] prev = new Node[1];  flattenList(head prev);  printList(head);  } }

Python

# A Python program to flatten a multi- # linked list depth-wise class Node: def __init__(self x): self.data = x self.next = None self.down = None def flatten_list(curr prev): if curr is None: return # Add the current element to the list. if prev[0] is not None: prev[0].next = curr prev[0] = curr # Store the next pointer next_node = curr.next # Recursively add the bottom list flatten_list(curr.down prev) # Recursively add the next list flatten_list(next_node prev) def print_list(head): curr = head while curr is not None: print(curr.data end=' ') curr = curr.next print() if __name__ == '__main__': # Create a hard coded multi-linked list. # 5 -> 10 -> 19 -> 28 # | | # 7 22 # | | # 8 50 # | # 30 head = Node(5) head.down = Node(7) head.down.down = Node(8) head.down.down.down = Node(30) head.next = Node(10) head.next.next = Node(19) head.next.next.down = Node(22) head.next.next.down.down = Node(50) head.next.next.next = Node(28) prev = [None] flatten_list(head prev) print_list(head)

// A C# program to flatten a multi- // linked list depth-wise using System; class Node {  public int data;  public Node next down;  public Node(int x) {  data = x;  next = down = null;  } } class GfG {  static void FlattenList(Node curr ref Node prev) {  if (curr == null)  return;  // Add the current element to the list.  if (prev != null)  prev.next = curr;  prev = curr;  // Store the next pointer  Node next = curr.next;  // Recursively add the bottom list  FlattenList(curr.down ref prev);  // Recursively add the next list  FlattenList(next ref prev);  }  static void PrintList(Node head) {  Node curr = head;  while (curr != null) {  Console.Write(curr.data + ' ');  curr = curr.next;  }  Console.WriteLine();  }  static void Main(string[] args) {  // Create a hard coded multi-linked list.  // 5 -> 10 -> 19 -> 28  // | |  // 7 22  // | |  // 8 50  // |  // 30  Node head = new Node(5);  head.down = new Node(7);  head.down.down = new Node(8);  head.down.down.down = new Node(30);  head.next = new Node(10);  head.next.next = new Node(19);  head.next.next.down = new Node(22);  head.next.next.down.down = new Node(50);  head.next.next.next = new Node(28);  Node prev = null;  FlattenList(head ref prev);  PrintList(head);  } }

JavaScript

// A Javascript program to flatten a multi- // linked list depth-wise class Node {  constructor(x) {  this.data = x;  this.next = null;  this.down = null;  } } function flattenList(curr prev) {  if (curr === null) return;  // Add the current element to the list.  if (prev[0] !== null) prev[0].next = curr;  prev[0] = curr;  // Store the next pointer  let next = curr.next;  // Recursively add the bottom list  flattenList(curr.down prev);  // Recursively add the next list  flattenList(next prev); } function printList(head) {  let curr = head;  while (curr !== null) {  console.log(curr.data);  curr = curr.next;  } } // Create a hard coded multi-linked list. // 5 -> 10 -> 19 -> 28 // | | // 7 22 // | | // 8 50 // | // 30 let head = new Node(5); head.down = new Node(7); head.down.down = new Node(8); head.down.down.down = new Node(30); head.next = new Node(10); head.next.next = new Node(19); head.next.next.down = new Node(22); head.next.next.down.down = new Node(50); head.next.next.next = new Node(28); let prev = [null]; flattenList(head prev); printList(head);

Çıkış

5 7 8 30 10 19 22 50 28

[Alternatif Yaklaşım] Yığın Kullanımı - O(n) Zaman ve O(n) Uzay

Yaklaşım, geçiş yapmaktır. çok düzeyli bağlantılı liste kullanarak yığın . Başlangıç tarihi: iterek the baş düğüm yığının üzerine. Daha sonra ise yığın boş değil pop üst düğüm ve onu işleyin. Her düğüm için itmek onun sonraki ve aşağı işaretçiler (eğer varsa) yığına. Bu süreç sırasında geçerli düğümü önceki düğüme bağlama listeyi düzleştirilmiş bir biçimde tutmak. Geçiş, tüm seviyelerdeki düğümlerin bir şekilde birbirine bağlanmasını sağlar. tek düzeyli bağlantılı liste derinlik açısından sıranın korunması.

C++

// A C++ program to flatten a multi- // linked list depth-wise using stack #include    using namespace std; class Node {  public:  int data;  Node *next;  Node *down;  Node(int x) {  data = x;  next = down = nullptr;  } }; void flattenList(Node *head) {  if (head == nullptr)  return;  stack<Node *> st;  st.push(head);  Node *prev = nullptr;  while (!st.empty()) {  Node *curr = st.top();  st.pop();  // Push the next node first  if (curr->next != nullptr)  st.push(curr->next);  // Push the bottom node into stack  if (curr->down != nullptr)  st.push(curr->down);  // Add the current element to the list  if (prev != nullptr)  prev->next = curr;  prev = curr;  } } void printList(Node *head) {  Node *curr = head;  while (curr != nullptr) {  cout << curr->data << ' ';  curr = curr->next;  }  cout << endl; } int main() {  // Create a hard coded multi-linked list.  // 5 -> 10 -> 19 -> 28  // | |  // 7 22  // | |  // 8 50  // |  // 30  Node *head = new Node(5);  head->down = new Node(7);  head->down->down = new Node(8);  head->down->down->down = new Node(30);  head->next = new Node(10);  head->next->next = new Node(19);  head->next->next->down = new Node(22);  head->next->next->down->down = new Node(50);  head->next->next->next = new Node(28);  flattenList(head);  printList(head);  return 0; }