Donat a llista enllaçada de mida N on cada node té dos enllaços: següent punter assenyalant el següent node i punter aleatori a qualsevol node aleatori de la llista. La tasca és crear un clon d'aquesta llista enllaçada a l'espai O(1), és a dir, sense cap espai addicional.
Exemples:
10 de 40
Entrada: Cap de la llista enllaçada a continuació
Sortida: Una nova llista enllaçada idèntica a la llista original.
[Enfocament esperat] Inserint nodes al lloc: O(3n) Temps i O (1) Espai
La idea és crear un duplicat d'un node i en comptes d'emmagatzemar-lo en una taula hash separada, podem inserir-lo entre el node original i el següent. Ara tindrem nous nodes en posicions alternatives. Ara per a node X el seu duplicat serà X->següent i el punter aleatori del duplicat hauria d'apuntar X->aleatori->següent (ja que aquest és el duplicat de X-> aleatori ). Per tant, itereu tota la llista enllaçada per actualitzar el punter aleatori de tots els nodes clonats i, a continuació, torneu a iterar per separar la llista enllaçada original i la llista enllaçada clonada.
Seguiu els passos esmentats a continuació per implementar la idea:
- Creeu la còpia de node 1 i inseriu-lo entre node 1 i node 2 a la llista enllaçada original creeu la còpia de node 2 i inseriu-lo entre 2 nd i 3 rd node i així successivament. Afegiu la còpia de N després de la Nthnode
- Connecteu el node de clons actualitzant els punters aleatoris.
- Separeu la llista enllaçada clonada de la llista original actualitzant els següents punters.
canviar el cas de java
A continuació es mostra la implementació si l'enfocament anterior:
C++// C++ code to Clone a linked list with next and random // pointer by Inserting Nodes In-place #include
// 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 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# 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 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);
Sortida
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)
Complexitat temporal: O(3n) perquè estem recorrent la llista enllaçada tres vegades.
Espai auxiliar: O(1) com que estem emmagatzemant tots els nodes clonats a la pròpia llista enllaçada original, no cal espai addicional.