fork download 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <unordered_map>
  5.  
  6. using namespace std;
  7.  
  8. struct Node{
  9. 	int val;
  10. 	Node* next;
  11. 	Node* child;
  12. 	Node(int value):val(value),next(NULL),child(NULL) {}
  13. };
  14.  
  15.  
  16. Node* createTree(){
  17. 	Node* head=new Node(1);
  18. 	head->next=new Node(2);
  19. 	head->next->next=new Node(3);
  20. 	head->next->next->next=new Node(7);
  21. 	head->next->next->next->next=new Node(8);
  22.  
  23. 	head->next->next->child=new Node(4);
  24. 	head->next->next->child->next=new Node(5);
  25. 	head->next->next->child->next->next=new Node(6);
  26.  
  27. 	head->next->next->child->next->child=new Node(50);
  28. 	head->next->next->child->next->child->next=new Node(51);
  29.  
  30. 	return head;
  31. }
  32.  
  33.  
  34. void printList(Node* head){
  35.  
  36. 	Node* current=head;
  37. 	while(current){
  38. 		cout<<current->val<<" ";
  39. 		if(current->child){
  40. 			cout<< "--";
  41. 			printList(current->child);
  42. 			cout<< "--";
  43. 		}
  44. 		current=current->next;
  45. 	}
  46. }
  47.  
  48. void restoreList(Node* head,unordered_map<Node*,Node*>& oldPositions ){
  49. 	if(oldPositions.size()==0) return;
  50.  
  51. 	Node* current=head;
  52. 	while(current){
  53. 		if(oldPositions.find(current)!=oldPositions.end()){
  54. 			Node* oldNext=oldPositions[current]->next;
  55. 			oldPositions[current]->next=NULL;
  56. 			restoreList(current->next, oldPositions);
  57. 			current->child=current->next;
  58. 			current->next=oldNext;
  59.  
  60.  
  61. 			oldPositions.erase(current);
  62. 		}
  63. 		current=current->next;
  64. 	}
  65.  
  66. }
  67.  
  68. //to be implemented
  69. Node* flatList(Node* head, Node*& tail, unordered_map<Node*,Node*>& oldPositions){
  70. 	if(NULL==head){
  71. 		tail=NULL;
  72. 		return NULL;
  73. 	}
  74.  
  75. 	Node* current=head;
  76. 	while(current){
  77.  
  78. 		Node* next=current->next;
  79.  
  80. 		if(current->child){
  81.  
  82. 			Node* flatTail=NULL;
  83. 			Node* flatHead=flatList(current->child, flatTail,oldPositions);
  84. 			oldPositions[current]=flatTail;
  85. 			current->child=NULL;
  86. 			current->next=flatHead;
  87. 			flatTail->next=next;
  88. 		}
  89.  
  90. 		if(current->next==NULL)
  91. 			tail=current;
  92. 		current=current->next;
  93. 	}
  94.  
  95. 	return head; 
  96. }
  97.  
  98.  
  99.  
  100. int main(int argc, char const *argv[])
  101. {
  102. 	Node* head=createTree();
  103. 	printList(head);
  104. 	Node* temp=NULL;
  105. 	unordered_map<Node*,Node*> oldPositions;
  106. 	Node* flatHead=flatList(head, temp, oldPositions);
  107. 	cout<<endl;
  108. 	printList(flatHead);
  109. 	restoreList(head, oldPositions);
  110. 	cout<<endl;
  111. 	printList(head);
  112. 	return 0;
  113. }
  114.  
Success #stdin #stdout 0s 3432KB
comments (?)
stdin 
Standard input is empty
stdout 
1 2 3 --4 5 --50 51 --6 --7 8 
1 2 3 4 5 50 51 6 7 8 
1 2 3 --4 5 --50 51 --6 --7 8
https://ideone.com/H1WUL0
flatten and restore list
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
secret

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!