Preveďte binárny strom na kruhový zoznam dvojitých odkazov
Vyskúšajte to na GfG Practice 
#practiceLinkDiv { display: none !important; }
Výstup
Výstup
#practiceLinkDiv { display: none !important; } Vzhľadom na a Binárny strom previesť na a Kruhový dvojito prepojený zoznam (Na mieste).
- Ľavý a pravý ukazovateľ v uzloch sa majú použiť ako predchádzajúci a nasledujúci ukazovateľ v konvertovanom kruhovom prepojenom zozname.
- Poradie uzlov v zozname musí byť rovnaké ako v poradí pre daný binárny strom.
- Prvý uzol Inorder traversal musí byť hlavným uzlom kruhového zoznamu.
Príklady:
Preveďte binárny strom na kruhový zoznam dvojitých odkazov pomocou rekurzie:
Cieľom je vytvoriť univerzálnu funkciu, ktorá zreťazí dva dané kruhové dvojité zoznamy
Pri riešení problému postupujte podľa nasledujúcich krokov:
- Rekurzívne konvertujte ľavý podstrom na kruhovú knižnicu DLL. Nech je prevedený zoznam leftList .
- Rekurzívne konvertujte pravý podstrom na kruhovú knižnicu DLL. Nech je prevedený zoznam .
- Vytvorte kruhový prepojený zoznam koreňov stromu a vytvorte ľavý a pravý koreňový bod na seba.
- zreťaziť leftList so zoznamom jedného koreňového uzla.
- Spájajte zoznam vytvorený v kroku vyššie s rightList .
Poznámka: Vyššie uvedený prístup prechádza stromom spôsobom Postorder. Môžeme sa prechádzať aj nepravidelným spôsobom. Najprv môžeme zreťaziť ľavý podstrom a koreň, potom zopakovať pravý podstrom a výsledok zreťaziť ľavokorenným zreťazením.
Ako zreťaziť dve kruhové knižnice DLL?
- Získajte posledný uzol ľavého zoznamu. Získanie posledného uzla je operácia O(1), pretože predchádzajúci ukazovateľ hlavičky ukazuje na posledný uzol zoznamu.
- Spojte ho s prvým uzlom pravého zoznamu
- Získajte posledný uzol druhého zoznamu
- Spojte ho s hlavičkou zoznamu.
Nižšie sú uvedené implementácie vyššie uvedenej myšlienky:
C++ // C++ Program to convert a Binary Tree // to a Circular Doubly Linked List #include using namespace std ; // To represents a node of a Binary Tree struct Node { struct Node * left * right ; int data ; }; // A function that appends rightList at the end // of leftList. Node * concatenate ( Node * leftList Node * rightList ) { // If either of the list is empty // then return the other list if ( leftList == NULL ) return rightList ; if ( rightList == NULL ) return leftList ; // Store the last Node of left List Node * leftLast = leftList -> left ; // Store the last Node of right List Node * rightLast = rightList -> left ; // Connect the last node of Left List // with the first Node of the right List leftLast -> right = rightList ; rightList -> left = leftLast ; // Left of first node points to // the last node in the list leftList -> left = rightLast ; // Right of last node refers to the first // node of the List rightLast -> right = leftList ; return leftList ; } // Function converts a tree to a circular Linked List // and then returns the head of the Linked List Node * bTreeToCList ( Node * root ) { if ( root == NULL ) return NULL ; // Recursively convert left and right subtrees Node * left = bTreeToCList ( root -> left ); Node * right = bTreeToCList ( root -> right ); // Make a circular linked list of single node // (or root). To do so make the right and // left pointers of this node point to itself root -> left = root -> right = root ; // Step 1 (concatenate the left list with the list // with single node i.e. current node) // Step 2 (concatenate the returned list with the // right List) return concatenate ( concatenate ( left root ) right ); } // Display Circular Link List void displayCList ( Node * head ) { cout < < 'Circular Linked List is : n ' ; Node * itr = head ; do { cout < < itr -> data < < ' ' ; itr = itr -> right ; } while ( head != itr ); cout < < ' n ' ; } // Create a new Node and return its address Node * newNode ( int data ) { Node * temp = new Node (); temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } // Driver Program to test above function int main () { Node * root = newNode ( 10 ); root -> left = newNode ( 12 ); root -> right = newNode ( 15 ); root -> left -> left = newNode ( 25 ); root -> left -> right = newNode ( 30 ); root -> right -> left = newNode ( 36 ); Node * head = bTreeToCList ( root ); displayCList ( head ); return 0 ; } // This code is contributed by Aditya Kumar (adityakumar129)
C // C Program to convert a Binary Tree // to a Circular Doubly Linked List #include #include // To represents a node of a Binary Tree typedef struct Node { struct Node * left * right ; int data ; } Node ; // A function that appends rightList at the end // of leftList. Node * concatenate ( Node * leftList Node * rightList ) { // If either of the list is empty // then return the other list if ( leftList == NULL ) return rightList ; if ( rightList == NULL ) return leftList ; // Store the last Node of left List Node * leftLast = leftList -> left ; // Store the last Node of right List Node * rightLast = rightList -> left ; // Connect the last node of Left List // with the first Node of the right List leftLast -> right = rightList ; rightList -> left = leftLast ; // Left of first node points to // the last node in the list leftList -> left = rightLast ; // Right of last node refers to the first // node of the List rightLast -> right = leftList ; return leftList ; } // Function converts a tree to a circular Linked List // and then returns the head of the Linked List Node * bTreeToCList ( Node * root ) { if ( root == NULL ) return NULL ; // Recursively convert left and right subtrees Node * left = bTreeToCList ( root -> left ); Node * right = bTreeToCList ( root -> right ); // Make a circular linked list of single node // (or root). To do so make the right and // left pointers of this node point to itself root -> left = root -> right = root ; // Step 1 (concatenate the left list with the list // with single node i.e. current node) // Step 2 (concatenate the returned list with the // right List) return concatenate ( concatenate ( left root ) right ); } // Display Circular Link List void displayCList ( Node * head ) { printf ( 'Circular Linked List is : n ' ); Node * itr = head ; do { printf ( '%d ' itr -> data ); itr = itr -> right ; } while ( head != itr ); printf ( ' n ' ); } // Create a new Node and return its address Node * newNode ( int data ) { Node * temp = ( Node * ) malloc ( sizeof ( Node )); temp -> data = data ; temp -> left = temp -> right = NULL ; return temp ; } // Driver Program to test above function int main () { Node * root = newNode ( 10 ); root -> left = newNode ( 12 ); root -> right = newNode ( 15 ); root -> left -> left = newNode ( 25 ); root -> left -> right = newNode ( 30 ); root -> right -> left = newNode ( 36 ); Node * head = bTreeToCList ( root ); displayCList ( head ); return 0 ; } // This code is contributed by Aditya Kumar (adityakumar129)
Java // Java Program to convert a Binary Tree to a // Circular Doubly Linked List // Node class represents a Node of a Tree class Node { int val ; Node left right ; public Node ( int val ) { this . val = val ; left = right = null ; } } // A class to represent a tree class Tree { Node root ; public Tree () { root = null ; } // concatenate both the lists and returns the head // of the List public Node concatenate ( Node leftList Node rightList ) { // If either of the list is empty then // return the other list if ( leftList == null ) return rightList ; if ( rightList == null ) return leftList ; // Store the last Node of left List Node leftLast = leftList . left ; // Store the last Node of right List Node rightLast = rightList . left ; // Connect the last node of Left List // with the first Node of the right List leftLast . right = rightList ; rightList . left = leftLast ; // left of first node refers to // the last node in the list leftList . left = rightLast ; // Right of last node refers to the first // node of the List rightLast . right = leftList ; // Return the Head of the List return leftList ; } // Method converts a tree to a circular // Link List and then returns the head // of the Link List public Node bTreeToCList ( Node root ) { if ( root == null ) return null ; // Recursively convert left and right subtrees Node left = bTreeToCList ( root . left ); Node right = bTreeToCList ( root . right ); // Make a circular linked list of single node // (or root). To do so make the right and // left pointers of this node point to itself root . left = root . right = root ; // Step 1 (concatenate the left list with the list // with single node i.e. current node) // Step 2 (concatenate the returned list with the // right List) return concatenate ( concatenate ( left root ) right ); } // Display Circular Link List public void display ( Node head ) { System . out . println ( 'Circular Linked List is :' ); Node itr = head ; do { System . out . print ( itr . val + ' ' ); itr = itr . right ; } while ( itr != head ); System . out . println (); } } // Driver Code class Main { public static void main ( String args [] ) { // Build the tree Tree tree = new Tree (); tree . root = new Node ( 10 ); tree . root . left = new Node ( 12 ); tree . root . right = new Node ( 15 ); tree . root . left . left = new Node ( 25 ); tree . root . left . right = new Node ( 30 ); tree . root . right . left = new Node ( 36 ); // head refers to the head of the Link List Node head = tree . bTreeToCList ( tree . root ); // Display the Circular LinkedList tree . display ( head ); } }
Python3 # Python3 Program to convert a Binary # Tree to a Circular Doubly Linked List class newNode : def __init__ ( self data ): self . data = data self . left = self . right = None # A function that appends rightList # at the end of leftList. def concatenate ( leftList rightList ): # If either of the list is empty # then return the other list if ( leftList == None ): return rightList if ( rightList == None ): return leftList # Store the last Node of left List leftLast = leftList . left # Store the last Node of right List rightLast = rightList . left # Connect the last node of Left List # with the first Node of the right List leftLast . right = rightList rightList . left = leftLast # Left of first node points to # the last node in the list leftList . left = rightLast # Right of last node refers to # the first node of the List rightLast . right = leftList return leftList # Function converts a tree to a circular # Linked List and then returns the head # of the Linked List def bTreeToCList ( root ): if ( root == None ): return None # Recursively convert left and # right subtrees left = bTreeToCList ( root . left ) right = bTreeToCList ( root . right ) # Make a circular linked list of single # node (or root). To do so make the # right and left pointers of this node # point to itself root . left = root . right = root # Step 1 (concatenate the left list # with the list with single # node i.e. current node) # Step 2 (concatenate the returned list # with the right List) return concatenate ( concatenate ( left root ) right ) # Display Circular Link List def displayCList ( head ): print ( 'Circular Linked List is :' ) itr = head first = 1 while ( head != itr or first ): print ( itr . data end = ' ' ) itr = itr . right first = 0 print () # Driver Code if __name__ == '__main__' : root = newNode ( 10 ) root . left = newNode ( 12 ) root . right = newNode ( 15 ) root . left . left = newNode ( 25 ) root . left . right = newNode ( 30 ) root . right . left = newNode ( 36 ) head = bTreeToCList ( root ) displayCList ( head ) # This code is contributed by PranchalK
C# // C# Program to convert a Binary Tree // to a Circular Doubly Linked List using System ; // Node class represents a Node of a Tree public class Node { public int val ; public Node left right ; public Node ( int val ) { this . val = val ; left = right = null ; } } // A class to represent a tree public class Tree { internal Node root ; public Tree () { root = null ; } // concatenate both the lists // and returns the head of the List public virtual Node concatenate ( Node leftList Node rightList ) { // If either of the list is empty // then return the other list if ( leftList == null ) { return rightList ; } if ( rightList == null ) { return leftList ; } // Store the last Node of left List Node leftLast = leftList . left ; // Store the last Node of right List Node rightLast = rightList . left ; // Connect the last node of Left List // with the first Node of the right List leftLast . right = rightList ; rightList . left = leftLast ; // left of first node refers to // the last node in the list leftList . left = rightLast ; // Right of last node refers to // the first node of the List rightLast . right = leftList ; // Return the Head of the List return leftList ; } // Method converts a tree to a circular // Link List and then returns the head // of the Link List public virtual Node bTreeToCList ( Node root ) { if ( root == null ) { return null ; } // Recursively convert left // and right subtrees Node left = bTreeToCList ( root . left ); Node right = bTreeToCList ( root . right ); // Make a circular linked list of single // node (or root). To do so make the // right and left pointers of this node // point to itself root . left = root . right = root ; // Step 1 (concatenate the left list with // the list with single node // i.e. current node) // Step 2 (concatenate the returned list // with the right List) return concatenate ( concatenate ( left root ) right ); } // Display Circular Link List public virtual void display ( Node head ) { Console . WriteLine ( 'Circular Linked List is :' ); Node itr = head ; do { Console . Write ( itr . val + ' ' ); itr = itr . right ; } while ( itr != head ); Console . WriteLine (); } } // Driver Code public class GFG { public static void Main ( string [] args ) { // Build the tree Tree tree = new Tree (); tree . root = new Node ( 10 ); tree . root . left = new Node ( 12 ); tree . root . right = new Node ( 15 ); tree . root . left . left = new Node ( 25 ); tree . root . left . right = new Node ( 30 ); tree . root . right . left = new Node ( 36 ); // head refers to the head of the Link List Node head = tree . bTreeToCList ( tree . root ); // Display the Circular LinkedList tree . display ( head ); } } // This code is contributed by Shrikant13
JavaScript < script > // javascript Program to convert a Binary Tree to a // Circular Doubly Linked List // Node class represents a Node of a Tree class Node { constructor ( val ) { this . val = val ; this . left = null ; this . right = null ; } } // A class to represent a var root = null ; // concatenate both the lists and returns the head // of the List function concatenate ( leftList rightList ) { // If either of the list is empty then // return the other list if ( leftList == null ) return rightList ; if ( rightList == null ) return leftList ; // Store the last Node of left List var leftLast = leftList . left ; // Store the last Node of right List var rightLast = rightList . left ; // Connect the last node of Left List // with the first Node of the right List leftLast . right = rightList ; rightList . left = leftLast ; // left of first node refers to // the last node in the list leftList . left = rightLast ; // Right of last node refers to the first // node of the List rightLast . right = leftList ; // Return the Head of the List return leftList ; } // Method converts a to a circular // Link List and then returns the head // of the Link List function bTreeToCList ( root ) { if ( root == null ) return null ; // Recursively convert left and right subtrees var left = bTreeToCList ( root . left ); var right = bTreeToCList ( root . right ); // Make a circular linked list of single node // (or root). To do so make the right and // left pointers of this node point to itself root . left = root . right = root ; // Step 1 (concatenate the left list with the list // with single node i.e. current node) // Step 2 (concatenate the returned list with the // right List) return concatenate ( concatenate ( left root ) right ); } // Display Circular Link List function display ( head ) { document . write ( 'Circular Linked List is :
' ); var itr = head ; do { document . write ( itr . val + ' ' ); itr = itr . right ; } while ( itr != head ); document . write (); } // Driver Code // Build the root = new Node ( 10 ); root . left = new Node ( 12 ); root . right = new Node ( 15 ); root . left . left = new Node ( 25 ); root . left . right = new Node ( 30 ); root . right . left = new Node ( 36 ); // head refers to the head of the Link List var head = bTreeToCList ( root ); // Display the Circular LinkedList display ( head ); // This code contributed by umadevi9616 < /script>
Výstup
Circular Linked List is : 25 12 30 10 36 15
Časová zložitosť: O(N) Keďže každý uzol je navštívený maximálne raz.
Pomocný priestor: O(log N) Dodatočný priestor sa používa v zásobníku rekurzných volaní, ktorý môže narásť až do maximálnej veľkosti logN, keďže ide o binárny strom.
Prevod binárneho stromu na kruhový zoznam dvojitých odkazov pomocou prechodu po poradí:
Myšlienkou je vykonať postupný prechod binárneho stromu. Počas prechodu v poradí sledujte predtým navštívený uzol v premennej povedzme predch . Pre každý navštívený uzol ho urobte ďalším z uzlov predch a nastavte predchádzajúci z tohto uzla ako predch .
Pri riešení problému postupujte podľa nasledujúcich krokov:
- Najprv preveďte binárny strom na zoznam s dvojitým odkazom, pozrite si tento príspevok Preveďte daný binárny strom na zoznam s dvojitým prepojením .
- Teraz preveďte tento dvojito prepojený zoznam na kruhový dvojito prepojený zoznam pripojením prvého a posledného uzla.
Nižšie je uvedená implementácia vyššie uvedeného prístupu.
C++ // A C++ program for in-place conversion of Binary Tree to // CDLL #include using namespace std ; /* A binary tree node has - data left and right pointers */ struct Node { int data ; Node * left ; Node * right ; }; // A utility function that converts given binary tree to // a doubly linked list // root --> the root of the binary tree // head --> head of the created doubly linked list Node * BTree2DoublyLinkedList ( Node * root Node ** head ) { // Base case if ( root == NULL ) return root ; // Initialize previously visited node as NULL. This is // static so that the same value is accessible in all // recursive calls static Node * prev = NULL ; // Recursively convert left subtree BTree2DoublyLinkedList ( root -> left head ); // Now convert this node if ( prev == NULL ) * head = root ; else { root -> left = prev ; prev -> right = root ; } prev = root ; // Finally convert right subtree BTree2DoublyLinkedList ( root -> right head ); return prev ; } // A simple recursive function to convert a given Binary // tree to Circular Doubly Linked List using a utility // function root --> Root of Binary Tree tail --> Pointer to // tail node of created circular doubly linked list Node * BTree2CircularDoublyLinkedList ( Node * root ) { Node * head = NULL ; Node * tail = BTree2DoublyLinkedList ( root & head ); // make the changes to convert a DLL to CDLL tail -> right = head ; head -> left = tail ; // return the head of the created CDLL return head ; } /* Helper function that allocates a new node with the given data and NULL left and right pointers. */ Node * newNode ( int data ) { Node * new_node = new Node ; new_node -> data = data ; new_node -> left = new_node -> right = NULL ; return ( new_node ); } /* Function to print nodes in a given circular doubly linked * list */ void printList ( Node * head ) { if ( head == NULL ) return ; Node * ptr = head ; do { cout < < ptr -> data < < ' ' ; ptr = ptr -> right ; } while ( ptr != head ); } /* Driver program to test above functions*/ int main () { // Let us create the tree shown in above diagram Node * root = newNode ( 10 ); root -> left = newNode ( 12 ); root -> right = newNode ( 15 ); root -> left -> left = newNode ( 25 ); root -> left -> right = newNode ( 30 ); root -> right -> left = newNode ( 36 ); // Convert to DLL Node * head = BTree2CircularDoublyLinkedList ( root ); // Print the converted list printList ( head ); return 0 ; } // This code was contributed by Abhijeet // Kumar(abhijeet19403)
Java // A Java program for in-place conversion of Binary Tree to // CDLL // A binary tree node has - data left pointer and right // pointer class Node { int data ; Node left right ; public Node ( int data ) { this . data = data ; left = right = null ; } } class BinaryTree { Node root ; // head --> Pointer to head node of created doubly // linked list Node head ; // Initialize previously visited node as NULL. This is // static so that the same value is accessible in all // recursive calls static Node prev = null ; // A simple utility recursive function to convert a // given Binary tree to Doubly Linked List root --> Root // of Binary Tree void BTree2DoublyLinkedList ( Node root ) { // Base case if ( root == null ) return ; // Recursively convert left subtree BTree2DoublyLinkedList ( root . left ); // Now convert this node if ( prev == null ) head = root ; else { root . left = prev ; prev . right = root ; } prev = root ; // Finally convert right subtree BTree2DoublyLinkedList ( root . right ); } // A simple function to convert a given binary tree to // Circular doubly linked list // using a utility function void BTree2CircularDoublyLinkedList ( Node root ) { BTree2DoublyLinkedList ( root ); // make the changes to convert a DLL to CDLL prev . right = head ; head . left = prev ; } /* Function to print nodes in a given doubly linked list */ void printList ( Node node ) { if ( node == null ) return ; Node curr = node ; do { System . out . print ( curr . data + ' ' ); curr = curr . right ; } while ( curr != node ); } // Driver program to test above functions public static void main ( String [] args ) { // Let us create the tree as shown in above diagram BinaryTree tree = new BinaryTree (); tree . root = new Node ( 10 ); tree . root . left = new Node ( 12 ); tree . root . right = new Node ( 15 ); tree . root . left . left = new Node ( 25 ); tree . root . left . right = new Node ( 30 ); tree . root . right . left = new Node ( 36 ); // convert to DLL tree . BTree2CircularDoublyLinkedList ( tree . root ); // Print the converted List tree . printList ( tree . head ); } } // This code has been contributed by Abhijeet // Kumar(abhijeet19403)
Python # A python program for in-place conversion of Binary Tree to DLL # A binary tree node has data left pointers and right pointers class Node : def __init__ ( self val ): self . data = val self . left = None self . right = None # head --> Pointer to head node of created doubly linked list head = None # Initialize previously visited node as NULL. This is # so that the same value is accessible in all recursive # calls prev = None # A simple recursive function to convert a given Binary tree # to Doubly Linked List # root --> Root of Binary Tree def BinaryTree2DoubleLinkedList ( root ): # Base case if ( root == None ): return # Recursively convert left subtree BinaryTree2DoubleLinkedList ( root . left ) # Now convert this node global prev head if ( prev == None ): head = root else : root . left = prev prev . right = root prev = root # Finally convert right subtree BinaryTree2DoubleLinkedList ( root . right ) # Function to print nodes in a given doubly linked list def printList ( node ): while ( node != None ): print ( node . data ) node = node . right # Driver program to test above functions # Let us create the tree as shown in above diagram root = Node ( 10 ) root . left = Node ( 12 ) root . right = Node ( 15 ) root . left . left = Node ( 25 ) root . left . right = Node ( 30 ) root . right . left = Node ( 36 ) # convert to DLL BinaryTree2DoubleLinkedList ( root ) # Print the converted List printList ( head ) # This code is contributed by adityamaharshi21.
C# // A C# program for in-place conversion of Binary Tree to // CDLL using System ; public class Node { public int data ; public Node left right ; public Node ( int data ) { this . data = data ; left = right = null ; } } public class BinaryTree { Node root ; // head --> Pointer to head node of created doubly // linked list Node head ; // Initialize previously visited node as NULL. This is // static so that the same value is accessible in all // recursive calls static Node prev = null ; // A simple utility recursive function to convert a // given Binary tree to Doubly Linked List root --> Root // of Binary Tree void BTree2DoublyLinkedList ( Node root ) { // Base case if ( root == null ) return ; // Recursively convert left subtree BTree2DoublyLinkedList ( root . left ); // Now convert this node if ( prev == null ) head = root ; else { root . left = prev ; prev . right = root ; } prev = root ; // Finally convert right subtree BTree2DoublyLinkedList ( root . right ); } // A simple function to convert a given binary tree to // Circular doubly linked list // using a utility function void BTree2CircularDoublyLinkedList ( Node root ) { BTree2DoublyLinkedList ( root ); // make the changes to convert a DLL to CDLL prev . right = head ; head . left = prev ; } /* Function to print nodes in a given doubly linked list */ void printList ( Node node ) { if ( node == null ) return ; Node curr = node ; do { Console . Write ( curr . data + ' ' ); curr = curr . right ; } while ( curr != node ); } static public void Main () { // Let us create the tree as shown in above diagram BinaryTree tree = new BinaryTree (); tree . root = new Node ( 10 ); tree . root . left = new Node ( 12 ); tree . root . right = new Node ( 15 ); tree . root . left . left = new Node ( 25 ); tree . root . left . right = new Node ( 30 ); tree . root . right . left = new Node ( 36 ); // convert to DLL tree . BTree2CircularDoublyLinkedList ( tree . root ); // Print the converted List tree . printList ( tree . head ); } } // This code is contributed by lokesh(lokeshmvs21).
JavaScript // A javascript program for in-place conversion of Binary Tree to DLL // A binary tree node has data left pointers and right pointers class Node { constructor ( val ) { this . data = val ; this . left = null ; this . right = null ; } } var root ; // head --> Pointer to head node of created doubly linked list var head ; // Initialize previously visited node as NULL. This is // so that the same value is accessible in all recursive // calls var prev = null ; // A simple recursive function to convert a given Binary tree // to Doubly Linked List // root --> Root of Binary Tree function BinaryTree2DoubleLinkedList ( root ) { // Base case if ( root == null ) return ; // Recursively convert left subtree BinaryTree2DoubleLinkedList ( root . left ); // Now convert this node if ( prev == null ) head = root ; else { root . left = prev ; prev . right = root ; } prev = root ; // Finally convert right subtree BinaryTree2DoubleLinkedList ( root . right ); } /* Function to print nodes in a given doubly linked list */ function printList ( node ) { while ( node != null ) { console . log ( node . data + ' ' ); node = node . right ; } } // Driver program to test above functions // Let us create the tree as shown in above diagram root = new Node ( 10 ); root . left = new Node ( 12 ); root . right = new Node ( 15 ); root . left . left = new Node ( 25 ); root . left . right = new Node ( 30 ); root . right . left = new Node ( 36 ); // convert to DLL BinaryTree2DoubleLinkedList ( root ); // Print the converted List printList ( head ); // This code is contributed by ishankhandelwals.
Výstup
25 12 30 10 36 15
Časová zložitosť: O(N) Ako každý uzol je navštívený maximálne raz.
Pomocný priestor: O (log N) Dodatočný priestor sa používa v zásobníku volaní rekurzívnych funkcií, ktorý môže narásť až do maximálnej veľkosti logN.
K tomuto prístupu prispelo Abhijeet Kumar
