Salīdzināt vairāku līmeņu saistīto sarakstu (pēc dziļuma)
Dots saistīts saraksts, kurā papildus nākamais rādītājs katram mezglam ir a bērns rādītājs, kas var norādīt vai nenorādīt uz atsevišķu sarakstu. Šajos pakārtotajos sarakstos var būt viens vai vairāki savus bērnus ražot a daudzlīmeņu saistītais saraksts. Ņemot vērā galvu no pirmais līmenis no saraksta. Uzdevums ir saplacināt sarakstu, lai visi mezgli parādītos a vienlīmeņa saistītais saraksts. Izlīdziniet sarakstu tā, lai visi mezgli pie pirmais līmenis vajadzētu nākt vispirms tad mezgli otrais līmenis un tā tālāk.
Piemēri:
Ievade:
Izvade: 1->4->6->2->5->7->3->8
Paskaidrojums: Daudzlīmeņu saistītais saraksts ir saplacināts, jo tajā nav pakārtotu norādes.
Mēs esam apsprieduši daudzlīmeņu saistītā saraksta saplacināšana kur mezgliem ir divas norādes uz leju un nākamo. Iepriekšējā ierakstā mēs saplacināts saistīto sarakstu līmenī. Kā saplacināt saistīto sarakstu, kad mums vienmēr ir jāapstrādā rādītājs uz leju pirms nākamā katrā mezglā.
Satura rādītājs
- [Paredzamā pieeja] Rekursijas izmantošana - O(n) laiks un O(n) telpa
- [Alternatīva pieeja] Stack izmantošana — O(n) laiks un O(n) telpa
[Paredzamā pieeja] Rekursijas izmantošana - O(n) laiks un O(n) telpa
C++Pieeja ir rekursīvi saplacināt a vairāklīmeņu saistīts sarakstu, šķērsojot katru mezglu un tā pakārtotos mezglus. Pirmkārt saplaciniet bērnu sarakstu izmantojot rekursiju. Kad bērnu saraksts ir saplacināts, pārejiet uz nākamais mezgls secībā. Šķērsošanas laikā uzturēt a atsauce uz iepriekš apmeklētais mezgls un saistīt to ar pašreizējo mezglu. Šis process nodrošina, ka visi dažādu līmeņu mezgli ir savienoti a viens lineārs saraksts vienlaikus saglabājot dziļuma secība.
// 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 );
Izvade
5 7 8 30 10 19 22 50 28
[Alternatīva pieeja] Stack izmantošana — O(n) laiks un O(n) telpa
C++Pieeja ir šķērsot daudzlīmeņu saistītais saraksts izmantojot a kaudze . Sāciet ar spiežot uz galvas mezgls uz kaudzes. Tad, kamēr kaudze nav tukša pop augšējo mezglu un apstrādājiet to. Katram mezglam spiediet tā nākamās un lejupvērstās norādes (ja tādi ir) uz kaudzes. Šī procesa laikā savienot pašreizējo mezglu ar iepriekšējo mezglu saraksta uzturēšana saplacinātā veidā. Šķērsošana nodrošina, ka mezgli no visiem līmeņiem ir savienoti a viena līmeņa saistītais saraksts saglabājot dziļuma kārtību.
// 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 );
Izvade
5 7 8 30 10 19 22 50 28
