给定一个链表，每个节点中有两个指针。第一个指针指向列表的下一个节点，而另一个指针是随机的，可以指向列表的任何节点。编写一个程序，在O（1）空间中克隆给定的列表，也就是说，没有任何额外的空间。 例如：
null
Input : Head of the below-linked list
![图片[1]-在O（1）空间中克隆带有下一个随机指针的链表-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/20200326193004/Screenshot-680.png)
Output :A new linked list identical to the original list.
在之前的帖子中 Set-1 和 第二套 文中讨论了各种方法，并给出了O（n）空间复杂度的实现方法。 在这篇文章中，我们将实现一个不需要额外空间的算法，如Set-1所述。 以下是算法：
- 创建节点1的副本并将其插入原始链表中的节点1和节点2之间，创建节点2的副本并将其插入2和3之间。以这种方式继续，在第N个节点后添加N的副本
- 现在用这种方式复制随机链接
original->next->random= original->random->next; /*TRAVERSE TWO NODES*/
- 这是因为“原始->下一步”只不过是原始->随机->下一步只是随机的副本。
- 现在，以这种方式在单个循环中恢复原始和复制链接列表。
original->next = original->next->next; copy->next = copy->next->next;
- 确保original->next为空并返回克隆列表
![图片[2]-在O（1）空间中克隆带有下一个随机指针的链表-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/20200326193538/Screenshot-6851.png)
下面是实现。
C++
// C++ program to clone a linked list with next // and arbit pointers in O(n) time #include <bits/stdc++.h> using namespace std; // Structure of linked list Node struct Node { int data; Node *next,*random; Node( int x) { data = x; next = random = NULL; } }; // Utility function to print the list. void print(Node *start) { Node *ptr = start; while (ptr) { cout << "Data = " << ptr->data << ", Random = " << ptr->random->data << endl; ptr = ptr->next; } } // This function clones a given linked list // in O(1) space Node* clone(Node *start) { Node* curr = start, *temp; // insert additional node after // every node of original list while (curr) { temp = curr->next; // Inserting node curr->next = new Node(curr->data); curr->next->next = temp; curr = temp; } curr = start; // adjust the random pointers of the // newly added nodes while (curr) { if (curr->next) curr->next->random = curr->random ? curr->random->next : curr->random; // move to the next newly added node by // skipping an original node curr = curr->next?curr->next->next:curr->next; } Node* original = start, *copy = start->next; // save the start of copied linked list temp = copy; // now separate the original list and copied list while (original && copy) { original->next = original->next? original->next->next : original->next; copy->next = copy->next?copy->next->next:copy->next; original = original->next; copy = copy->next; } return temp; } // Driver code int main() { Node* start = new Node(1); start->next = new Node(2); start->next->next = new Node(3); start->next->next->next = new Node(4); start->next->next->next->next = new Node(5); // 1's random points to 3 start->random = start->next->next; // 2's random points to 1 start->next->random = start; // 3's and 4's random points to 5 start->next->next->random = start->next->next->next->next; start->next->next->next->random = start->next->next->next->next; // 5's random points to 2 start->next->next->next->next->random = start->next; cout << "Original list : " ; print(start); cout << "Cloned list : " ; Node *cloned_list = clone(start); print(cloned_list); return 0; } |
JAVA
// Java program to clone a linked list with next // and arbit pointers in O(n) time class GfG { // Structure of linked list Node static class Node { int data; Node next, random; Node( int x) { data = x; next = random = null ; } } // Utility function to print the list. static void print(Node start) { Node ptr = start; while (ptr != null ) { System.out.println( "Data = " + ptr.data + ", Random = " + ptr.random.data); ptr = ptr.next; } } // This function clones a given // linked list in O(1) space static Node clone(Node start) { Node curr = start, temp = null ; // insert additional node after // every node of original list while (curr != null ) { temp = curr.next; // Inserting node curr.next = new Node(curr.data); curr.next.next = temp; curr = temp; } curr = start; // adjust the random pointers of the // newly added nodes while (curr != null ) { if (curr.next != null ) curr.next.random = (curr.random != null ) ? curr.random.next : curr.random; // move to the next newly added node by // skipping an original node curr = curr.next.next; } Node original = start, copy = start.next; // save the start of copied linked list temp = copy; // now separate the original list and copied list while (original != null ) { original.next =original.next.next; copy.next = (copy.next != null ) ? copy.next.next : copy.next; original = original.next; copy = copy.next; } return temp; } // Driver code public static void main(String[] args) { Node start = new Node( 1 ); start.next = new Node( 2 ); start.next.next = new Node( 3 ); start.next.next.next = new Node( 4 ); start.next.next.next.next = new Node( 5 ); // 1's random points to 3 start.random = start.next.next; // 2's random points to 1 start.next.random = start; // 3's and 4's random points to 5 start.next.next.random = start.next.next.next.next; start.next.next.next.random = start.next.next.next.next; // 5's random points to 2 start.next.next.next.next.random = start.next; System.out.println( "Original list : " ); print(start); System.out.println( "Cloned list : " ); Node cloned_list = clone(start); print(cloned_list); } } // This code is contributed by Prerna Saini. |
C#
// C# program to clone a linked list with // next and arbit pointers in O(n) time using System; class GFG { // Structure of linked list Node class Node { public int data; public Node next, random; public Node( int x) { data = x; next = random = null ; } } // Utility function to print the list. static void print(Node start) { Node ptr = start; while (ptr != null ) { Console.WriteLine( "Data = " + ptr.data + ", Random = " + ptr.random.data); ptr = ptr.next; } } // This function clones a given // linked list in O(1) space static Node clone(Node start) { Node curr = start, temp = null ; // insert additional node after // every node of original list while (curr != null ) { temp = curr.next; // Inserting node curr.next = new Node(curr.data); curr.next.next = temp; curr = temp; } curr = start; // adjust the random pointers of // the newly added nodes while (curr != null ) { if (curr.next != null ) curr.next.random = (curr.random != null ) ? curr.random.next : curr.random; // move to the next newly added node // by skipping an original node curr = (curr.next != null ) ? curr.next.next : curr.next; } Node original = start, copy = start.next; // save the start of copied linked list temp = copy; // now separate the original list // and copied list while (original != null && copy != null ) { original.next = (original.next != null )? original.next.next : original.next; copy.next = (copy.next != null ) ? copy.next.next : copy.next; original = original.next; copy = copy.next; } return temp; } // Driver code public static void Main(String[] args) { Node start = new Node(1); start.next = new Node(2); start.next.next = new Node(3); start.next.next.next = new Node(4); start.next.next.next.next = new Node(5); // 1's random points to 3 start.random = start.next.next; // 2's random points to 1 start.next.random = start; // 3's and 4's random points to 5 start.next.next.random = start.next.next.next.next; start.next.next.next.random = start.next.next.next.next; // 5's random points to 2 start.next.next.next.next.random = start.next; Console.WriteLine( "Original list : " ); print(start); Console.WriteLine( "Cloned list : " ); Node cloned_list = clone(start); print(cloned_list); } } // This code has been contributed // by Rajput-Ji |
python
'''Python program to clone a linked list with next and arbitrary pointers''' '''Done in O(n) time with O(1) extra space''' class Node: '''Structure of linked list node''' def __init__( self , data): self .data = data self . next = None self .random = None def clone(original_root): '''Clone a doubly linked list with random pointer''' '''with O(1) extra space''' '''Insert additional node after every node of original list''' curr = original_root while curr ! = None : new = Node(curr.data) new. next = curr. next curr. next = new curr = curr. next . next '''Adjust the random pointers of the newly added nodes''' curr = original_root while curr ! = None : curr. next .random = curr.random. next curr = curr. next . next '''Detach original and duplicate list from each other''' curr = original_root dup_root = original_root. next while curr. next ! = None : tmp = curr. next curr. next = curr. next . next curr = tmp return dup_root def print_dlist(root): '''Function to print the doubly linked list''' curr = root while curr ! = None : print ( 'Data =' , curr.data, ', Random =' , curr.random.data) curr = curr. next ####### Driver code ####### '''Create a doubly linked list''' original_list = Node( 1 ) original_list. next = Node( 2 ) original_list. next . next = Node( 3 ) original_list. next . next . next = Node( 4 ) original_list. next . next . next . next = Node( 5 ) '''Set the random pointers''' # 1's random points to 3 original_list.random = original_list. next . next # 2's random points to 1 original_list. next .random = original_list # 3's random points to 5 original_list. next . next .random = original_list. next . next . next . next # 4's random points to 5 original_list. next . next . next .random = original_list. next . next . next . next # 5's random points to 2 original_list. next . next . next . next .random = original_list. next '''Print the original linked list''' print ( 'Original list:' ) print_dlist(original_list) '''Create a duplicate linked list''' cloned_list = clone(original_list) '''Print the duplicate linked list''' print ( 'Cloned list:' ) print_dlist(cloned_list) '''This code is contributed by Shashank Singh''' |
Javascript
<script> // Javascript program to clone a linked list with next // and arbit pointers in O(n) time // Structure of linked list Node class Node { constructor(x) { this .data = x; this .next = this .random = null ; } } // Utility function to print the list. function print(start) { var ptr = start; while (ptr != null ) { document.write( "Data = " + ptr.data + ", Random = " + ptr.random.data+ "<br/>" ); ptr = ptr.next; } } // This function clones a given // linked list in O(1) space function clone(start) { var curr = start, temp = null ; // insert additional node after // every node of original list while (curr != null ) { temp = curr.next; // Inserting node curr.next = new Node(curr.data); curr.next.next = temp; curr = temp; } curr = start; // adjust the random pointers of the // newly added nodes while (curr != null ) { if (curr.next != null ) curr.next.random = (curr.random != null ) ? curr.random.next : curr.random; // move to the next newly added node by // skipping an original node curr = (curr.next != null ) ? curr.next.next : curr.next; } var original = start, copy = start.next; // save the start of copied linked list temp = copy; // now separate the original list and copied list while (original != null && copy != null ) { original.next = (original.next != null ) ? original.next.next : original.next; copy.next = (copy.next != null ) ? copy.next.next : copy.next; original = original.next; copy = copy.next; } return temp; } // Driver code var start = new Node(1); start.next = new Node(2); start.next.next = new Node(3); start.next.next.next = new Node(4); start.next.next.next.next = new Node(5); // 1's random points to 3 start.random = start.next.next; // 2's random points to 1 start.next.random = start; // 3's and 4's random points to 5 start.next.next.random = start.next.next.next.next; start.next.next.next.random = start.next.next.next.next; // 5's random points to 2 start.next.next.next.next.random = start.next; document.write( "Original list : <br/>" ); print(start); document.write( "<br>" ); document.write( "Cloned list : <br/>" ); var cloned_list = clone(start); print(cloned_list); // This code contributed by aashish1995 </script> |
输出
Original list : Data = 1, Random = 3Data = 2, Random = 1Data = 3, Random = 5Data = 4, Random = 5Data = 5, Random = 2Cloned list : Data = 1, Random = 3Data = 2, Random = 1Data = 3, Random = 5Data = 4, Random = 5Data = 5, Random = 2
本文由 阿什图什·库马尔 如果你喜欢Geeksforgek，并且想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
