Klonuoti susietą sąrašą su sekančiu ir atsitiktiniu žymekliu O(1) erdvėje
Atsižvelgiant į a susietas sąrašas dydžio N kur kiekvienas mazgas turi dvi nuorodas: kitas rodyklė rodydamas į kitą mazgą ir atsitiktinis rodyklė į bet kurį atsitiktinį sąrašo mazgą. Užduotis yra sukurti šio susieto sąrašo kloną O(1) erdvėje, ty be papildomos vietos.
Pavyzdžiai:
Įvestis: Žemiau esančio sąrašo vadovas
Išvestis: Naujas susietas sąrašas, identiškas pirminiam sąrašui.
[Numatomas požiūris] įterpiant mazgus vietoje – O(3n) laikas ir O(1) erdvė
Idėja yra sukurti mazgo dublikatą ir užuot saugoję jį atskiroje maišos lentelėje, galime įterpti jį tarp pradinio mazgo ir kito mazgo. Dabar turėsime naujus mazgus kitose vietose. Dabar už a mazgas X bus jos dublikatas X-> kitas o atsitiktinė dublikato rodyklė turėtų rodyti į X->atsitiktinis->kitas (nes tai yra dublikatas X-> atsitiktinis ). Taigi kartokite visą susietą sąrašą, kad atnaujintumėte atsitiktinę visų klonuotų mazgų žymeklį, o tada kartokite dar kartą, kad atskirtumėte pradinį susietą sąrašą ir klonuotą susietą sąrašą.
Norėdami įgyvendinti idėją, atlikite toliau nurodytus veiksmus:
- Sukurkite kopiją mazgas 1 ir įdėkite jį tarp mazgas 1 ir mazgas 2 pradiniame susietų sąraše sukurkite kopiją mazgas 2 ir įdėkite jį tarp 2 nd ir 3 rd mazgas ir pan. Po raidės N pridėkite N kopiją th mazgas
- Prijunkite klono mazgą atnaujindami atsitiktines nuorodas.
- Atskirkite klonuotą susietą sąrašą nuo pradinio sąrašo, atnaujindami kitas nuorodas.
Toliau pateikiamas įgyvendinimas, jei aukščiau nurodytas metodas:
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 );
Išvestis
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)
Laiko sudėtingumas: O(3n) nes mes perkeliame susietą sąrašą tris kartus.
Pagalbinė erdvė: O(1) nes saugome visus klonuotus mazgus pačiame pradiniame susietame sąraše, nereikia papildomos vietos.
