fork download
copy 
  1. #include <iostream>
  2. #include <unordered_map>
  3. using namespace std;
  4.  
  5. class Node {
  6. public:
  7. 	int val;
  8. 	Node* next;
  9. 	Node* random;
  10. 	Node(int _val, Node* _next = nullptr, Node* _random = nullptr) {
  11. 		val = _val;
  12. 		next = _next;
  13. 		random = _random;
  14. 	}
  15. };
  16.  
  17. class Solution {
  18. public:
  19. 	Node* copyRandomList(Node* head) {
  20. 		if (!head)
  21. 			return nullptr;
  22.  
  23. 		unordered_map<Node*, Node*> node_map;
  24. 		Node* copy_head = nullptr;
  25. 		Node** copy = &copy_head;
  26. 		Node* node = head;
  27.  
  28. 		do {
  29. 			*copy = new Node(node->val/*, nullptr, nullptr*/);
  30. 			node_map.insert(make_pair(node, *copy));
  31. 			copy = &((*copy)->next);
  32. 			node = node->next;
  33. 		}
  34. 		while (node);
  35.  
  36. 		node = copy_head;
  37.  
  38. 		do {
  39. 			if (head->random)
  40. 				node->random = node_map[head->random];
  41. 			node = node->next;
  42. 			head = head->next;
  43. 		}
  44. 		while (head);
  45.  
  46. 		return copy_head;
  47. 	}
  48. };
  49.  
  50. void printList(Node *head) {
  51. 	while (head) {
  52. 		cout << head << " val=" << head->val << " random=";
  53. 		if (head->random)
  54. 			cout << head->random->val << endl;
  55. 		else
  56. 			cout << "null";
  57. 		head = head->next;
  58. 	}
  59. }
  60.  
  61. int main() {
  62. 	Node node1(1);
  63. 	Node node2(2);
  64.  
  65. 	node1.next = &node2;
  66. 	node1.random = &node2;
  67. 	node2.random = &node2;
  68.  
  69. 	printList(&node1);
  70. 	cout << endl;
  71.  
  72.  
  73. 	Node *copy = Solution{}.copyRandomList(&node1);
  74. 	printList(copy);
  75.  
  76. 	return 0;
  77. }
Success #stdin #stdout 0s 4192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0x7ffd5b614dc0 val=1 random=2
0x7ffd5b614de0 val=2 random=2

0x5602cc0e6e80 val=1 random=2
0x5602cc0e6ee0 val=2 random=2
https://ideone.com/fK5oZ7
language:
C++ (gcc 8.3)
created:
6 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!