שכפל רשימה מקושרת עם המצביע הבא והאקראי ברווח O(1).
בהינתן א רשימה מקושרת של גודל נ כאשר לכל צומת יש שני קישורים: המצביע הבא מצביע על הצומת הבא ו מצביע אקראי לכל צומת אקראי ברשימה. המשימה היא ליצור שיבוט של רשימה מקושרת זו במרחב O(1), כלומר ללא רווח נוסף.
דוגמאות:
קֶלֶט: ראש הרשימה המקושרת למטה
תְפוּקָה: רשימה מקושרת חדשה זהה לרשימה המקורית.
[גישה צפויה] על ידי הוספת צמתים במקום - O(3n) זמן ו-O(1) מרחב
הרעיון הוא ליצור כפיל של צומת ובמקום לאחסן בטבלת hash נפרדת נוכל להכניס אותו בין הצומת המקורי לצומת הבא. כעת יהיו לנו צמתים חדשים בעמדות חלופיות. עכשיו עבור א צומת X הכפיל שלו יהיה X->הבא ועל המצביע האקראי של הכפילות צריך להצביע X->אקראי->הבא (מכיוון שזה השכפול של X->אקראי ). אז חזרו על כל הרשימה המקושרת כדי לעדכן את המצביע האקראי של כל הצמתים המשובטים ואז חזרו שוב כדי להפריד בין הרשימה המקושרת המקורית לבין הרשימה המקושרת המשובטת.
בצע את השלבים המוזכרים להלן כדי ליישם את הרעיון:
- צור את העותק של צומת 1 ולהכניס אותו בין צומת 1 ו צומת 2 ברשימה המקושרת המקורית צור את העותק של צומת 2 ולהכניס אותו בין 2 נד ו 3 rd צומת וכן הלאה. הוסף את העותק של N אחרי ה-N ה' צוֹמֶת
- חבר את צומת השיבוט על ידי עדכון המצביעים האקראיים.
- הפרד את הרשימה המקושרת המשובטת מהרשימה המקורית על ידי עדכון המצביעים הבאים.
להלן היישום אם הגישה לעיל:
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 );
תְפוּקָה
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)
מורכבות זמן: O(3n) כי אנחנו חוצים את הרשימה המקושרת שלוש פעמים.
מרחב עזר: O(1) מכיוון שאנו מאחסנים את כל הצמתים המשובטים ברשימה המקושרת המקורית עצמה, אין צורך ברווח נוסף.
