logo

TechCodeview

Изравняване на многостепенен свързан списък (по отношение на дълбочината)

Предвид свързан списък, където в допълнение към  следващия  указател всеки възел има a  дете  указател, който може или не може да сочи към отделен списък. Тези дъщерни списъци може да имат  един или повече  свои собствени деца за производство на a  многостепенно  свързан списък. Като се има предвид  главата  на  първо ниво  от списъка. Задачата е да  изравнявам  списъка, така че всички възли да се показват в a  едноетажна  свързан списък. Изравнете списъка по начин, по който всички възли в  първо ниво  трябва да дойде  първи след това възли на  второ  ниво и така нататък.

Примери:



вход:

2_5' title=


Изход: 1->4->6->2->5->7->3->8
Обяснение: Многостепенният свързан списък е сплескан, тъй като няма дъщерни указатели.



дълъг към низ java

Обсъждали сме изравняване на многостепенен свързан списък където възлите имат два указателя надолу и следващия. В предишната публикация ние сплескан по ниво. Как да изравним свързан списък, когато винаги трябва да обработваме показалец надолу преди следващия във всеки възел.

Съдържание

[Очакван подход] Използване на рекурсия - O(n) време и O(n) пространство

Подходът е към рекурсивно изравнявам a свързан на много нива списък чрез преминаване през всеки възел и неговите дъщерни възли. Първо изравняване на дъщерния списък използване на рекурсия. След като дъщерният списък е изравнен, продължете към следващ възел в последователността. По време на преминаването поддържайте a справка към посетен преди това възел и го свържете към текущия възел. Този процес гарантира, че всички възли от различни нива са свързани в a един линеен списък при запазване на ред в дълбочина.



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);

Изход 
5 7 8 30 10 19 22 50 28

[Алтернативен подход] Използване на стек - O(n) време и O(n) пространство

Подходът е да се премине през многостепенен свързан списък с помощта на a стек . Започнете от бутане на главен възел върху стека. Тогава, докато на стекът не е празен поп горния възел и го обработете. За всеки възел тласък неговото указатели следващ и надолу (ако съществуват) върху стека. По време на този процес свържете текущия възел с предишния възел поддържане на списъка в сплескана форма. Преминаването гарантира, че възлите от всички нива са свързани в a свързан списък на едно ниво запазване на реда в дълбочина.

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);

Изход 
5 7 8 30 10 19 22 50 28