fork download
copy 
  1. /* given a doubly linked list, one which points to the next
  2. element and other points randomly to some other node, we have to
  3. clone the original list */
  4.  
  5. #include<iostream>
  6. using namespace std;
  7.  
  8. class Node{
  9. 	public:
  10. 		int data;
  11. 		Node* next;
  12. 		Node* rand;
  13. };
  14.  
  15. Node* head = NULL;
  16. Node* tail = NULL;
  17.  
  18. void add_end(int data){
  19. 	Node* temp = new Node;
  20. 	temp->data = data;
  21. 	temp->next = NULL;
  22. 	temp->rand = NULL;
  23. 	if(head == NULL){
  24. 		head = temp;
  25. 		tail = temp;
  26. 		return;
  27. 	}
  28. 	tail->next = temp;
  29. 	tail = temp;
  30. }
  31.  
  32. Node* add_between(Node* temp){
  33. 	Node* temp2 = new Node;
  34. 	temp2->data = temp->data;
  35. 	temp2->next = temp->next;
  36. 	temp2->rand = NULL;
  37. 	return temp2;
  38. }
  39.  
  40.  
  41. Node* clone_list(){
  42. 	Node* temp = head;
  43. 	Node* temp2;
  44. 	while(temp){
  45. 		temp->next = add_between(temp);
  46. 		temp = temp->next->next;
  47. 	}
  48. 	temp = head;
  49. 	while(temp){
  50. 		temp->next->rand = temp->rand->next;
  51. 		temp = temp->next->next;
  52. 	}
  53. 	temp = head;
  54. 	temp2 = head->next;
  55. 	Node* final = temp2;
  56. 	while(temp && temp2){
  57. 		temp->next = temp2->next;
  58. 		temp = temp->next;
  59. 		if(temp){
  60. 			temp2->next = temp->next;
  61. 			temp2 = temp2->next;
  62. 		}
  63. 	}
  64. 	return final;
  65. }
  66.  
  67. void print_list(Node* head){
  68. 	Node* temp = head;
  69. 	while(temp){
  70. 		cout<<temp->data<<" ";
  71. 		temp = temp->next;
  72. 	}
  73. 	cout<<endl;
  74. }
  75.  
  76. void print_rand(Node* head){
  77. 	Node* temp = head;
  78. 	while(temp){
  79. 		cout<<temp->rand->data<<" ";
  80. 		temp = temp->next;
  81. 	}
  82. 	cout<<endl;
  83. }
  84.  
  85. int main(){
  86. 	add_end(1);
  87. 	add_end(2);
  88. 	add_end(3);
  89. 	add_end(4);
  90. 	add_end(5);
  91. 	// making the random pointer point to any element
  92. 	head->rand = head->next->next; // 1 rand points to 3
  93. 	head->next->rand = head->next->next->next; // 2 rand points to 4
  94. 	head->next->next->rand = head; // 3 rand points to 1
  95. 	head->next->next->next->rand = head->next; // 4 rand points to 2
  96. 	tail->rand = head; // 5 rand points to 1
  97.  
  98. 	Node* final = clone_list();
  99. 	cout<<"The cloned list is"<<endl;
  100. 	print_list(final); // should print 1 2 3 4 5
  101. 	cout<<"The random pointers of list are"<<endl;
  102. 	print_rand(final); // should print 3 4 1 2 1
  103. 	return 0;
  104.  
  105. }
  106.  
Success #stdin #stdout 0s 4556KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The cloned list is
1 2 3 4 5 
The random pointers of list are
3 4 1 2 1
https://ideone.com/iinUVO
language:
C++ (gcc 8.3)
created:
4 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!