Kloon een gekoppelde lijst met volgende en willekeurige aanwijzer in O(1)-ruimte
Gegeven een gekoppelde lijst van grootte N waarbij elk knooppunt twee links heeft: volgende wijzer wijzend naar het volgende knooppunt en willekeurige wijzer naar een willekeurig knooppunt in de lijst. De taak is om een kloon van deze gekoppelde lijst in O(1)-ruimte te maken, d.w.z. zonder extra ruimte.
Voorbeelden:
Invoer: Hoofd van de onderstaande gelinkte lijst
Uitgang: Een nieuwe gekoppelde lijst die identiek is aan de oorspronkelijke lijst.
[Verwachte aanpak] door knooppunten op hun plaats in te voegen – O(3n) tijd en O(1) ruimte
Het idee is om een duplicaat van een knooppunt te maken en in plaats van het in een aparte hashtabel op te slaan, kunnen we deze tussen het oorspronkelijke knooppunt en het volgende knooppunt invoegen. Nu zullen we nieuwe knooppunten op alternatieve posities hebben. Nu voor een knooppunt X het duplicaat zal zijn X->volgende en de willekeurige aanwijzer van het duplicaat moet naar wijzen X->willekeurig->volgende (want dat is het duplicaat van X -> willekeurig ). Herhaal dus de gehele gekoppelde lijst om de willekeurige aanwijzer van alle gekloonde knooppunten bij te werken en herhaal vervolgens opnieuw om de oorspronkelijke gekoppelde lijst en de gekloonde gekoppelde lijst te scheiden.
Volg de onderstaande stappen om het idee te implementeren:
- Maak de kopie van knooppunt 1 en plaats deze ertussen knooppunt 1 En knooppunt 2 in de originele gekoppelde lijst, maak er een kopie van knooppunt 2 en plaats deze ertussen 2 nl En 3 rd knooppunt enzovoort. Voeg de kopie van N toe na de N e knooppunt
- Verbind het kloonknooppunt door de willekeurige wijzers bij te werken.
- Scheid de gekloonde gekoppelde lijst van de originele lijst door de volgende verwijzingen bij te werken.
Hieronder vindt u de implementatie als de bovenstaande aanpak:
C++ // C++ code to Clone a linked list with next and random // pointer by Inserting Nodes In-place #include using namespace std ; struct Node { int data ; Node * next * random ; Node ( int x ) { data = x ; next = random = NULL ; } }; Node * cloneLinkedList ( Node * head ) { if ( head == NULL ) { return NULL ; } // Create new nodes and insert them next to // the original nodes Node * curr = head ; while ( curr != NULL ) { Node * newNode = new Node ( curr -> data ); newNode -> next = curr -> next ; curr -> next = newNode ; curr = newNode -> next ; } // Set the random pointers of the new nodes curr = head ; while ( curr != NULL ) { if ( curr -> random != NULL ) curr -> next -> random = curr -> random -> next ; curr = curr -> next -> next ; } // Separate the new nodes from the original nodes curr = head ; Node * clonedHead = head -> next ; Node * clone = clonedHead ; while ( clone -> next != NULL ) { // Update the next nodes of original node // and cloned node curr -> next = curr -> next -> next ; clone -> next = clone -> next -> next ; // Move pointers of original as well as // cloned linked list to their next nodes curr = curr -> next ; clone = clone -> next ; } curr -> next = NULL ; clone -> next = NULL ; return clonedHead ; } // Function to print the linked list void printList ( Node * head ) { while ( head != NULL ) { cout < < head -> data < < '(' ; if ( head -> random ) cout < < head -> random -> data < < ')' ; else cout < < 'null' < < ')' ; if ( head -> next != NULL ) cout < < ' -> ' ; head = head -> next ; } cout < < endl ; } int main () { // Creating a linked list with random pointer Node * head = new Node ( 1 ); head -> next = new Node ( 2 ); head -> next -> next = new Node ( 3 ); head -> next -> next -> next = new Node ( 4 ); head -> next -> next -> next -> next = new Node ( 5 ); head -> random = head -> next -> next ; head -> next -> random = head ; head -> next -> next -> random = head -> next -> next -> next -> next ; head -> next -> next -> next -> random = head -> next -> next ; head -> next -> next -> next -> next -> random = head -> next ; // Print the original list cout < < 'Original linked list: n ' ; printList ( head ); // Function call Node * clonedList = cloneLinkedList ( head ); cout < < 'Cloned linked list: n ' ; printList ( clonedList ); return 0 ; }
Java // Java code to Clone a linked list with next and random // pointer by Inserting Nodes In-place class Node { int data ; Node next random ; Node ( int x ) { data = x ; next = random = null ; } } class GfG { // Function to clone the linked list static Node cloneLinkedList ( Node head ) { if ( head == null ) { return null ; } // Create new nodes and insert them next to the original nodes Node curr = head ; while ( curr != null ) { Node newNode = new Node ( curr . data ); newNode . next = curr . next ; curr . next = newNode ; curr = newNode . next ; } // Set the random pointers of the new nodes curr = head ; while ( curr != null ) { if ( curr . random != null ) { curr . next . random = curr . random . next ; } curr = curr . next . next ; } // Separate the new nodes from the original nodes curr = head ; Node clonedHead = head . next ; Node clone = clonedHead ; while ( clone . next != null ) { // Update the next nodes of original node // and cloned node curr . next = curr . next . next ; clone . next = clone . next . next ; // Move pointers of original and cloned // linked list to their next nodes curr = curr . next ; clone = clone . next ; } curr . next = null ; clone . next = null ; return clonedHead ; } // Function to print the linked list public static void printList ( Node head ) { while ( head != null ) { System . out . print ( head . data + '(' ); if ( head . random != null ) { System . out . print ( head . random . data ); } else { System . out . print ( 'null' ); } System . out . print ( ')' ); if ( head . next != null ) { System . out . print ( ' -> ' ); } head = head . next ; } System . out . println (); } public static void main ( String [] args ) { // Creating a linked list with random pointer Node head = new Node ( 1 ); head . next = new Node ( 2 ); head . next . next = new Node ( 3 ); head . next . next . next = new Node ( 4 ); head . next . next . next . next = new Node ( 5 ); head . random = head . next . next ; head . next . random = head ; head . next . next . random = head . next . next . next . next ; head . next . next . next . random = head . next . next ; head . next . next . next . next . random = head . next ; // Print the original list System . out . println ( 'Original linked list:' ); printList ( head ); // Function call Node clonedList = cloneLinkedList ( head ); System . out . println ( 'Cloned linked list:' ); printList ( clonedList ); } }
Python # Python code to Clone a linked list with next and random # pointer by Inserting Nodes In-place class Node : def __init__ ( self x ): self . data = x self . next = None self . random = None # Function to clone the linked list def clone_linked_list ( head ): if head is None : return None # Create new nodes and insert them next to # the original nodes curr = head while curr is not None : new_node = Node ( curr . data ) new_node . next = curr . next curr . next = new_node curr = new_node . next # Set the random pointers of the new nodes curr = head while curr is not None : if curr . random is not None : curr . next . random = curr . random . next curr = curr . next . next # Separate the new nodes from the original nodes curr = head cloned_head = head . next clone = cloned_head while clone . next is not None : # Update the next nodes of original node # and cloned node curr . next = curr . next . next clone . next = clone . next . next # Move pointers of original as well as # cloned linked list to their next nodes curr = curr . next clone = clone . next curr . next = None clone . next = None return cloned_head # Function to print the linked list def print_list ( head ): while head is not None : print ( f ' { head . data } (' end = '' ) if head . random : print ( f ' { head . random . data } )' end = '' ) else : print ( 'null)' end = '' ) if head . next is not None : print ( ' -> ' end = '' ) head = head . next print () if __name__ == '__main__' : # Creating a linked list with random pointer head = Node ( 1 ) head . next = Node ( 2 ) head . next . next = Node ( 3 ) head . next . next . next = Node ( 4 ) head . next . next . next . next = Node ( 5 ) head . random = head . next . next head . next . random = head head . next . next . random = head . next . next . next . next head . next . next . next . random = head . next . next head . next . next . next . next . random = head . next # Print the original list print ( 'Original linked list:' ) print_list ( head ) # Function call cloned_list = clone_linked_list ( head ) print ( 'Cloned linked list:' ) print_list ( cloned_list )
C# // C# code to Clone a linked list with next and random // pointer by Inserting Nodes In-place using System ; using System.Collections.Generic ; public class Node { public int Data ; public Node next Random ; public Node ( int x ) { Data = x ; next = Random = null ; } } class GfG { static Node CloneLinkedList ( Node head ) { if ( head == null ) return null ; // Create new nodes and insert them next to // the original nodes Node curr = head ; while ( curr != null ) { Node newNode = new Node ( curr . Data ); newNode . next = curr . next ; curr . next = newNode ; curr = newNode . next ; } // Set the random pointers of the new nodes curr = head ; while ( curr != null ) { if ( curr . Random != null ) curr . next . Random = curr . Random . next ; curr = curr . next . next ; } // Separate the new nodes from the original nodes curr = head ; Node clonedHead = head . next ; Node clone = clonedHead ; while ( clone . next != null ) { // Update the next nodes of original node // and cloned node curr . next = curr . next . next ; clone . next = clone . next . next ; // Move pointers of original as well as // cloned linked list to their next nodes curr = curr . next ; clone = clone . next ; } curr . next = null ; clone . next = null ; return clonedHead ; } // Function to print the linked list static void PrintList ( Node head ) { while ( head != null ) { Console . Write ( head . Data + '(' ); if ( head . Random != null ) Console . Write ( head . Random . Data + ')' ); else Console . Write ( 'null)' ); if ( head . next != null ) Console . Write ( ' -> ' ); head = head . next ; } Console . WriteLine (); } public static void Main () { // Creating a linked list with random pointer Node head = new Node ( 1 ); head . next = new Node ( 2 ); head . next . next = new Node ( 3 ); head . next . next . next = new Node ( 4 ); head . next . next . next . next = new Node ( 5 ); head . Random = head . next . next ; head . next . Random = head ; head . next . next . Random = head . next . next . next . next ; head . next . next . next . Random = head . next . next ; head . next . next . next . next . Random = head . next ; // Print the original list Console . WriteLine ( 'Original linked list:' ); PrintList ( head ); Node clonedList = CloneLinkedList ( head ); Console . WriteLine ( 'Cloned linked list:' ); PrintList ( clonedList ); } }
JavaScript // JavaScript code to Clone a linked list with next and random // pointer by Inserting Nodes In-place class Node { constructor ( data ) { this . data = data ; this . next = null ; this . random = null ; } } function cloneLinkedList ( head ) { if ( head === null ) { return null ; } // Create new nodes and insert them next to the // original nodes let curr = head ; while ( curr !== null ) { let newNode = new Node ( curr . data ); newNode . next = curr . next ; curr . next = newNode ; curr = newNode . next ; } // Set the random pointers of the new nodes curr = head ; while ( curr !== null ) { if ( curr . random !== null ) { curr . next . random = curr . random . next ; } curr = curr . next . next ; } // Separate the new nodes from the original nodes curr = head ; let clonedHead = head . next ; let clone = clonedHead ; while ( clone . next !== null ) { // Update the next nodes of original node and cloned node curr . next = curr . next . next ; clone . next = clone . next . next ; // Move pointers of original as well as cloned // linked list to their next nodes curr = curr . next ; clone = clone . next ; } curr . next = null ; clone . next = null ; return clonedHead ; } // Function to print the linked list function printList ( head ) { let result = '' ; while ( head !== null ) { result += head . data + '(' ; result += head . random ? head . random . data : 'null' ; result += ')' ; if ( head . next !== null ) { result += ' -> ' ; } head = head . next ; } console . log ( result ); } // Creating a linked list with random pointer let head = new Node ( 1 ); head . next = new Node ( 2 ); head . next . next = new Node ( 3 ); head . next . next . next = new Node ( 4 ); head . next . next . next . next = new Node ( 5 ); head . random = head . next . next ; head . next . random = head ; head . next . next . random = head . next . next . next . next ; head . next . next . next . random = head . next . next ; head . next . next . next . next . random = head . next ; // Print the original list console . log ( 'Original linked list:' ); printList ( head ); let clonedList = cloneLinkedList ( head ); console . log ( 'Cloned linked list:' ); printList ( clonedList );
Uitvoer
Original linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2) Cloned linked list: 1(3) -> 2(1) -> 3(5) -> 4(3) -> 5(2)
Tijdcomplexiteit: O(3n) omdat we de gekoppelde lijst drie keer doorkruisen.
Hulpruimte: O(1) omdat we alle gekloonde knooppunten in de originele gekoppelde lijst zelf opslaan, is er geen extra ruimte vereist.
