logo

TechCodeview

Izravnajte povezani popis na više razina (dubinski)

S obzirom na povezani popis gdje pored  sljedeći  pokazivač svaki čvor ima a  dijete  pokazivač koji može ali ne mora pokazivati ​​na zasebnu listu. Ovi podređeni popisi mogu imati  jedan ili više  vlastita djeca za proizvodnju a  višerazinski  povezani popis. S obzirom na  glava  od  prva razina  popisa. Zadatak je da se  izravnati  popis tako da se svi čvorovi pojavljuju u a  jednorazinski  povezani popis. Poravnajte popis na način da svi čvorovi na  prva razina  treba doći  prvi zatim čvorovi  drugi  razina i tako dalje.

Primjeri:



Ulazni:

2_5' title=


Izlaz: 1->4->6->2->5->7->3->8
Obrazloženje: Višerazinska povezana lista je spljoštena jer nema pokazivača na djecu.



Raspravljali smo izravnavanje višerazinske povezane liste gdje čvorovi imaju dva pokazivača dolje i dalje. U prethodnom postu mi spljošten povezani popis nivoski. Kako izravnati povezani popis kada uvijek trebamo obraditi pokazivač prema dolje prije sljedećeg u svakom čvoru.

Sadržaj

[Očekivani pristup] Korištenje rekurzije - O(n) vremena i O(n) prostora

Pristup je da se rekurzivno izravnati a povezan na više razina popis obilazeći svaki čvor i njegove podređene čvorove. Prvi izravnati popis djece pomoću rekurzije. Nakon što je popis djece izravnan, prijeđite na sljedeći čvor u nizu. Tijekom obilaska održavajte a referenca prema prethodno posjećeni čvor i povežite ga s trenutnim čvorom. Ovaj proces osigurava da su svi čvorovi s različitih razina povezani u a jedna linearna lista uz očuvanje dubinski poredak.



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)
C# 
// 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);

Izlaz 
5 7 8 30 10 19 22 50 28

[Alternativni pristup] Korištenje hrpe - O(n) vremena i O(n) prostora

Pristup je prijeći preko višerazinski povezani popis pomoću a stog . Počni od guranje the glavni čvor na stog. Zatim dok je stog nije prazan pop gornji čvor i obradite ga. Za svaki čvor gurnuti njegov next i down pokazivači (ako postoje) na stog. Tijekom ovog procesa povezati trenutni čvor s prethodnim čvorom održavanje popisa u spljoštenom obliku. Traversal osigurava da su čvorovi sa svih razina povezani u a jednorazinski povezani popis čuvajući dubinski red.

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; }
Java 
// A Java program to flatten a multi- // linked list depth-wise using stack import java.util.Stack; class Node {  int data;  Node next down;  Node(int x) {  data = x;  next = down = null;  } } class GfG {  static void flattenList(Node head) {  if (head == null)  return;  Stack<Node> stack = new Stack<>();  stack.push(head);  Node prev = null;  while (!stack.isEmpty()) {  Node curr = stack.pop();  // Push the next node first  if (curr.next != null)  stack.push(curr.next);  // Push the bottom node into stack  if (curr.down != null)  stack.push(curr.down);  // Add the current element to the list  if (prev != null)  prev.next = curr;  prev = curr;  }  }  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);  flattenList(head);  printList(head);  } }
Python 
# A Python program to flatten a multi- # linked list depth-wise using stack class Node: def __init__(self x): self.data = x self.next = None self.down = None def flatten_list(head): if head is None: return stack = [head] prev = None while stack: curr = stack.pop() # Push the next node first if curr.next: stack.append(curr.next) # Push the bottom node into stack if curr.down: stack.append(curr.down) # Add the current element to the list if prev: prev.next = curr prev = curr def print_list(head): curr = head while curr: 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) flatten_list(head) print_list(head)
C# 
// A C# program to flatten a multi- // linked list depth-wise using stack using System; using System.Collections.Generic; class Node {  public int data;  public Node next down;  public Node(int x) {  data = x;  next = down = null;  } } class GfG {  static void FlattenList(Node head) {  if (head == null)  return;  Stack<Node> stack = new Stack<Node>();  stack.Push(head);  Node prev = null;  while (stack.Count > 0) {  Node curr = stack.Pop();  // Push the next node first  if (curr.next != null)  stack.Push(curr.next);  // Push the bottom node into stack  if (curr.down != null)  stack.Push(curr.down);  // Add the current element to the list  if (prev != null)  prev.next = curr;  prev = curr;  }  }  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);    FlattenList(head);  PrintList(head);  } }
JavaScript 
// A Javascript program to flatten a multi- // linked list depth-wise using stack class Node {  constructor(x) {  this.data = x;  this.next = null;  this.down = null;  } } function flattenList(head) {  if (head === null) return;  let stack = [head];  let prev = null;  while (stack.length > 0) {  let curr = stack.pop();  // Push the next node first  if (curr.next !== null) stack.push(curr.next);  // Push the bottom node into stack  if (curr.down !== null) stack.push(curr.down);  // Add the current element to the list  if (prev !== null) prev.next = curr;  prev = curr;  } } 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); flattenList(head); printList(head);

Izlaz 
5 7 8 30 10 19 22 50 28