Bağlantılı bir listeyi O(1) alanında sonraki ve rastgele işaretçiyle klonlayın
Verilen bir bağlantılı liste boyutta N her düğümün iki bağlantısı vardır: sonraki işaretçi bir sonraki düğüme işaret eder ve rastgele işaretçi listedeki herhangi bir rastgele düğüme. Görev, bu bağlantılı listenin bir kopyasını O(1) alanında, yani fazladan boşluk olmadan oluşturmaktır.
Örnekler:
Giriş: Aşağıdaki bağlantılı listenin başı
Çıkış: Orijinal listeyle aynı olan yeni bir bağlantılı liste.
[Beklenen Yaklaşım] Düğümleri Yerine Ekleyerek – O(3n) Zaman ve O(1) Uzay
Buradaki fikir, bir düğümün kopyasını oluşturmak ve ayrı bir karma tablosunda saklamak yerine onu orijinal düğüm ile bir sonraki düğüm arasına yerleştirebilmektir. Artık alternatif konumlarda yeni düğümlerimiz olacak. Şimdi bir düğüm X onun kopyası olacak X->sonraki ve kopyanın rastgele işaretçisi şunu göstermelidir: X->rastgele->sonraki (bunun kopyası olduğundan X->rastgele ). Bu nedenle, tüm klonlanmış düğümlerin rastgele işaretçisini güncellemek için bağlantılı listenin tamamını yineleyin ve ardından orijinal bağlantılı listeyi ve klonlanmış bağlantılı listeyi ayırmak için tekrar yineleyin.
Fikri uygulamak için aşağıda belirtilen adımları izleyin:
- Kopyasını oluştur düğüm 1 ve arasına yerleştirin düğüm 1 Ve düğüm 2 orijinal Bağlantılı Listede aşağıdakilerin kopyasını oluşturun: düğüm 2 ve arasına yerleştirin 2 ve Ve 3 üçüncü düğüm vb. N'nin kopyasını N'den sonra ekleyin bu düğüm
- Rastgele işaretçileri güncelleyerek klon düğümünü bağlayın.
- Sonraki işaretçileri güncelleyerek klonlanmış bağlantılı listeyi orijinal listeden ayırın.
Yukarıdaki yaklaşımın uygulanması aşağıdadır:
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 );
Çıkış
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)
Zaman Karmaşıklığı: O(3n) çünkü bağlantılı listede üç kez dolaşıyoruz.
Yardımcı Alan: O(1) tüm klonlanmış düğümleri orijinal bağlantılı listede sakladığımız için fazladan alana gerek yoktur.
