fork(1) download
copy 
  1. #include <iostream>
  2. #include <unordered_map>
  3.  
  4. using namespace std;
  5.  
  6. // Definition of Complex Nodes
  7. struct ComplexNode
  8. {
  9.     int value;
  10.     ComplexNode* next;
  11.     ComplexNode* arbit;
  12.     ComplexNode():next(NULL),arbit(NULL){}
  13. };
  14.  
  15. // Create a complex node linked list for test
  16. ComplexNode* CreateComplexNodeLinkedList()
  17. {
  18.     // Create nodes
  19.     ComplexNode* node1 = new ComplexNode();
  20.     ComplexNode* node2 = new ComplexNode();
  21.     ComplexNode* node3 = new ComplexNode();
  22.     ComplexNode* node4 = new ComplexNode();
  23.     ComplexNode* node5 = new ComplexNode();
  24.     // Set value to nodes
  25.     node1->value = 1;
  26.     node2->value = 2;
  27.     node3->value = 3;
  28.     node4->value = 4;
  29.     node5->value = 5;
  30.     // Link them with next
  31.     node1->next = node2;
  32.     node2->next = node3;
  33.     node3->next = node4;
  34.     node4->next = node5;
  35.     // Link them with arbit
  36.     node1->arbit = node3;
  37.     node2->arbit = node1;
  38.     node3->arbit = node5;
  39.     node4->arbit = node3;
  40.     node5->arbit = node2;
  41.  
  42.     return node1;
  43. }
  44.  
  45. ComplexNode* CloneByHashing(ComplexNode* pHead)
  46. {
  47.     if (pHead == NULL)
  48.         return NULL;
  49.  
  50.     unordered_map<ComplexNode*,ComplexNode*> ptrMap;
  51.  
  52.     ComplexNode* pClonedHead = new ComplexNode();
  53.     pClonedHead->value = pHead->value;
  54.     pClonedHead->arbit = pHead->arbit;
  55.     ptrMap[pHead] = pClonedHead;
  56.  
  57.     ComplexNode* pCloned = pClonedHead; 
  58.     ComplexNode* pCurrent = pHead->next;
  59.  
  60.     while (pCurrent != NULL)
  61.     {
  62.         pCloned->next = new ComplexNode();
  63.         ptrMap[pCurrent] = pCloned->next;
  64.         pCloned->next->value = pCurrent->value;
  65.         pCloned->next->arbit = pCurrent->arbit;
  66.  
  67.         pCloned = pCloned->next;
  68.         pCurrent = pCurrent->next;
  69.     }
  70.  
  71.     ComplexNode* pClonedCurrent = pClonedHead;
  72.     ComplexNode* temp = NULL;
  73.     while (pClonedCurrent != NULL)
  74.     { 
  75.         temp = pClonedCurrent->arbit;
  76.         pClonedCurrent->arbit = ptrMap.find(temp)->second;
  77.         pClonedCurrent = pClonedCurrent->next;
  78.     }
  79.  
  80.     return pClonedHead;
  81. }
  82.  
  83. // Unitily function
  84. void PrintList(ComplexNode *head)
  85. {
  86.     ComplexNode *ptr = head;
  87.  
  88.     while (ptr != NULL)
  89.     {
  90.         cout << "node address = " << ptr << ","
  91.              << " node value = " << ptr->value << ","
  92.              << " node arbit address = " << ptr->arbit << ","
  93.              <<  " node arbit value = " << ptr->arbit->value << endl;
  94.  
  95.         ptr = ptr->next;
  96.     }
  97.     cout << endl;
  98. }
  99.  
  100. int main(int argc, const char * argv[])
  101. {
  102.     ComplexNode *head = CreateComplexNodeLinkedList();
  103.     ComplexNode *headCloned2 = CloneByHashing(head);
  104.  
  105.  
  106.     PrintList(headCloned2);
  107.  
  108.     return 0;
  109. }
Success #stdin #stdout 0s 3432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
node address = 0x973e088, node value = 1, node arbit address = 0x973e0c8, node arbit value = 3
node address = 0x973e0a8, node value = 2, node arbit address = 0x973e088, node arbit value = 1
node address = 0x973e0c8, node value = 3, node arbit address = 0x973e108, node arbit value = 5
node address = 0x973e0e8, node value = 4, node arbit address = 0x973e0c8, node arbit value = 3
node address = 0x973e108, node value = 5, node arbit address = 0x973e0a8, node arbit value = 2
https://ideone.com/lCl9E1
language:
C++14 (gcc 8.3)
created:
9 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!