fork download
copy 
  1. #include <iostream>
  2. using namespace std;
  3.  
  4.  
  5. class Node {
  6. 	public:
  7. 		int value;
  8. 		Node *next;
  9. 		Node(int val) {
  10. 			this->value = val;
  11. 			this->next = NULL;
  12. 		}
  13. };
  14.  
  15. Node* createList() {
  16. 	Node *root = new Node(1);
  17. 	root->next = new Node(2);			
  18. 	root->next->next = new Node(3);
  19. 	root->next->next->next = new Node(4);
  20. 	root->next->next->next->next = new Node(5);
  21. 	root->next->next->next->next->next = new Node(6);
  22. 	root->next->next->next->next->next->next = new Node(7);
  23. 	root->next->next->next->next->next->next->next = new Node(8);
  24. 	return root;
  25. }
  26.  
  27. Node *findMiddleNode(Node *root) {
  28. 	Node* sp = root;
  29. 	Node* fp = root;
  30. 	Node* prev = NULL;
  31. 	while (fp != NULL && fp->next != NULL) {
  32. 		prev = sp;
  33. 		sp = sp->next;
  34. 		fp = fp->next->next;
  35. 	}
  36. 	return prev;
  37. }
  38.  
  39. Node *reverList(Node* root) {
  40. 	Node* prev = NULL;
  41. 	Node* next = root->next;
  42. 	Node* curr = root;
  43. 	while (curr != NULL) {
  44. 		curr->next = prev;
  45. 		prev = curr;
  46. 		curr = next;
  47. 		if (next != NULL) {
  48. 			next = next->next;
  49. 		}
  50. 	}
  51. 	return prev;
  52. }
  53.  
  54. Node *rearrangeList(Node *root) {
  55. 	Node* prev;
  56. 	Node* fList = root;
  57. 	Node* n = findMiddleNode(root);
  58. 	Node* sListStart = n->next;
  59. 	// terminate the first list
  60. 	n->next = NULL;
  61. 	Node *sList = reverList(sListStart);
  62.  
  63. 	while (fList != NULL && sList != NULL) {
  64. 		Node* temp = fList->next;
  65. 		fList->next = sList;
  66. 		sList = sList->next;
  67. 		fList->next->next = temp;
  68. 		prev = fList;
  69. 		fList = temp;
  70. 	}
  71.  
  72. 	if (fList == NULL && sList != NULL) {
  73. 		prev->next = sList;
  74. 	}
  75.  
  76. 	if  (fList != NULL && sList != NULL) {
  77. 		fList->next = sList;
  78. 	}
  79. 	return root;
  80. }
  81.  
  82. int main() {
  83. 	Node* root = createList();
  84. 	Node *finalList = rearrangeList(root);
  85.  
  86. 	while (finalList != NULL) {
  87. 		cout << finalList->value << " ";
  88. 		finalList = finalList->next;
  89. 	}
  90. 	return 0;
  91. }
Success #stdin #stdout 0.01s 5476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
middleNode: 4
1 8 2 7 3 6 4 5
https://ideone.com/09l8lZ
language:
C++ (gcc 8.3)
created:
1 year 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!