fork download
copy 
  1. #include<bits/stdc++.h>
  2. //#include<leetcode.h>
  3. #define null NULL
  4. #define endl '\n'
  5. #define ll long long
  6. using namespace std;
  7. #define goF(i, a, b) for(int i=a; i<b; i++)
  8. #define goB(i, a, b) for(int i=a; i>=b; i--)
  9.  
  10. class Node{
  11. public:
  12. 	int data;
  13. 	Node* next;
  14. 	Node(int data){
  15. 		this->data = data;
  16. 		this->next = null;
  17. 	}
  18. 	~Node(){//Iterative Destructor
  19. 		delete next;
  20. 	}
  21. };
  22.  
  23. Node* takeInput(){
  24. 	int data; cin>>data;
  25. 	Node* head = null, *tail = null;
  26.  
  27. 	while(data != -1){
  28. 		Node* newNode = new Node(data);
  29.  
  30. 		if(head == null){
  31. 			head = newNode;
  32. 			tail = newNode;
  33. 		}else{
  34. 			tail->next = newNode;
  35. 			tail = newNode;
  36. 		}
  37.  
  38. 		cin>>data;
  39. 	}
  40.  
  41. 	return head;
  42. }
  43. Node* createLinkedList(vector<int>& arr){
  44. 	int pos = 0;
  45. 	Node* head = null, *tail = null;
  46.  
  47. 	while(pos < (int)arr.size()){
  48. 		Node* newNode = new Node(arr[pos]);
  49.  
  50. 		if(head == null){
  51. 			head = newNode;
  52. 			tail = newNode;
  53. 		}else{
  54. 			tail->next = newNode;
  55. 			tail = newNode;
  56. 		}
  57.  
  58. 		pos++;
  59. 	}
  60.  
  61. 	return head;
  62. }
  63. void deleteLinkedList(Node* &head){
  64.     Node* current = head;
  65.     while(current != null){
  66.         Node* next = current->next;
  67.         delete current;
  68.         current = next;
  69.     }
  70.     delete head;
  71. }
  72.  
  73. void print_iter(Node* head){
  74. 	Node* current = head;
  75. 	while(current != null){
  76. 		cout<<current->data<<' ';
  77. 		current = current->next;
  78. 	}
  79. }
  80. int length_iter(Node* head){
  81. 	int count = 0;
  82. 	Node* current = head;
  83. 	while(current != null){
  84. 		current = current->next;
  85. 		count++;
  86. 	}
  87. 	return count;
  88. }
  89.  
  90. Node* evenAfterOdd(Node* head){
  91. 	if(head == null) return head;
  92.  
  93. 	Node* oddHead = null, *oddTail = null, *evenHead = null, *evenTail = null;
  94. 	Node* current = head;
  95.  
  96. 	//Start traversing the Linked List
  97. 	while(current != null){
  98.  
  99. 		//Node* newNode = new Node(current->data);
  100. 		Node* newNode = new Node(current->data);
  101.  
  102. 		if(current->data % 2 == 1){
  103. 			if(oddHead == null){
  104. 				oddHead = newNode;
  105. 				oddTail = newNode;
  106. 			}else{
  107. 				oddTail->next = newNode;
  108. 				oddTail = newNode;
  109. 			}
  110. 		}else{//i.e. the current node's data is EVEN
  111. 			if(evenHead == null){
  112. 				evenHead = newNode;
  113. 				evenTail = newNode;
  114. 			}else{
  115. 				evenTail->next = newNode;
  116. 				evenTail = newNode;
  117. 			}
  118. 		}
  119.  
  120. 		//head = head->next;
  121. 		current = current->next;
  122. 	}
  123.  
  124. 	//Now you have 2 linked list one with all odd nodes and one with all the even ones
  125.  
  126. 	//But precautious: Security Checks
  127. 	//1. Check 1: odd one was never updated, in that case return the evenHead
  128. 	if(oddHead == null){
  129. 		return evenHead; //evenHead could be empty or non empty as well
  130. 	}else{//otherwise, connect the one with all ODD nodes with the one with all EVEN nodes
  131. 		oddTail->next = evenHead;
  132. 	}
  133.  
  134. 	if(evenHead != null){
  135. 		evenTail->next = null;
  136. 	}
  137.  
  138. 	return oddHead;
  139. }
  140. Node* swapNodes(Node* head, int i, int j){
  141.  
  142. 	if(i == j) return head; //if both the positions are same, nothing to be swapped, return original head
  143.  
  144. 	int length = length_iter(head);
  145.  
  146. 	if(i < 0 or i >= length or j < 0 or j >= length) return head;
  147. //	We need 4 pointers, that will serve the following purposes
  148. //		c1: node at position i, p1: node previous to c1
  149. //		c2: node at position j, p2: node previous to c2
  150. 	Node *p1 = null, *c1 = null, *p2 = null, *c2 = null;
  151.  
  152.  
  153. //	Run a traversal module with two pointers 'current' and 'previous'
  154. //	to set up (p1, c1), (p2, c2)
  155. 	int pos = 0;
  156. 	Node *current = head, *previous = null;
  157. 	while(current != null and (c1 == null or c2 == null)){
  158. 		//The reason we're using "and (c1 == null or c2 == null)"
  159. 		//is because we want to quit traversing the linked list
  160. 		//as soon as we find both c1 and c2
  161. 		//or in other words as long as either of them are not set
  162.  
  163. 		if(pos == i){
  164. 			p1 = previous;
  165. 			c1 = current;
  166. 		}
  167. 		else if(pos == j){
  168. 			p2 = previous;
  169. 			c2 = current;
  170. 		}
  171.  
  172. 		previous = current; //always update previous first
  173. 		current = current->next; //followed by current
  174. 		pos++; //and then increase your counter
  175.  
  176. 	}
  177.  
  178.  
  179.  
  180. //	Once you place the pointers in their appropriate positions, just change links in 3 easy steps
  181. //	1. Connect p1's next to c2
  182. //	2. Connect p2's next to c1
  183. //	3. Connect c2's next to c1's next and c1's next to c2's next
  184.  
  185. 	//1. Connect p1's next to c2
  186. 	//but keep in mind that there's a possibility that p1 could still be null,
  187. 	//=> p1 never got updated => i == 0
  188. 	//So, after swapping c2's gonna be the new head
  189. 	if(p1 != null) p1->next = c2;
  190. 	else head = c2;
  191.  
  192. 	//2. Connect p2's next to c1 (taking care of the edge case)
  193. 	//Similarly here as well, if p2 is still null then that => j == 0
  194. 	//so after swapping c1's gonna be the new head
  195. 	if(p2 != null) p2->next = c1;
  196. 	else head = c1;
  197. 	//3. Connect c2's next to c1's next and c1's next to c2's next
  198. 	Node* c2sNext = c2->next;
  199. 	c2->next = c1->next;
  200. 	c1->next = c2sNext;
  201.  
  202.  
  203.  
  204. 	return head; //and finally we're done!
  205. }
  206.  
  207. Node* reverse_iter(Node* head){
  208. 	Node* current = head, *previous = null;
  209.  
  210. 	while(current != null){
  211. 		Node* currentsNext = current->next;
  212. 		current->next = previous;
  213.  
  214. 		previous = current;
  215. 		current = currentsNext;
  216. 	}
  217. 	return previous;
  218. }
  219. Node* reverse_recur(Node* head){
  220. 	//Base Case:
  221. 	if(head == null or head->next == null) return head;
  222.  
  223. 	//Call recursion on current's next
  224. 	Node* reversedHead = reverse_recur(head->next);
  225.  
  226. 	//Now Post-Processing:
  227. 	//2nd Node's gonna be the tail of the reversed linked list (key)
  228. 	Node* tail = head->next;
  229. 	tail->next = head; //make it point to head
  230. 	head->next = null; //vvi to severe the ties
  231.  
  232. 	return reversedHead;
  233. }
  234. Node* kReverse(Node* head, int k){//similar to reverse_iter()
  235.  
  236. 	if(k == 0 or k == 1) return head;
  237.  
  238. 	int count = 0;
  239. 	Node* prev = null, *current = head;
  240. 	Node* currentsNext = null; //very important to declare outside as that'll help us determine if there's any node left after reversing the first k set of nodes
  241.  
  242. 	//Iteratively reverse the first k set of nodes
  243. 	while(count < k and current != null){
  244. 		currentsNext = current->next;
  245. 		current->next = prev;
  246.  
  247. 		prev = current;
  248. 		current = currentsNext;
  249. 		count++;
  250. 	}
  251.  
  252. 	//then if there's anymore node left (current's next != null)
  253. 	//then recursively reverse the remaining list, i.e. call kReverse() on current's next
  254. 	if(currentsNext != null){
  255. 		head->next = kReverse(currentsNext, k);
  256. 	}
  257.  
  258. 	return prev;
  259. }
  260.  
  261.  
  262. Node* delete_recur(Node* head, int pos){
  263. 	//Base Case:
  264. 	if(head == null) return head;
  265.  
  266.  
  267. 	//Pre-Processing: If the deletion is at head, then take care of that
  268. 	if(pos == 1){
  269. 		Node* newHead = head->next;
  270. 		head->next = null;
  271. 		delete head;
  272. 		return newHead;
  273. 	}
  274.  
  275.  
  276. 	//otherwise pass on to recursion
  277. 	Node* updatedHead = delete_recur(head->next, pos-1);
  278.  
  279. 	//then connect it to your exisiting head in the post-processing part
  280. 	head->next = updatedHead;
  281.  
  282. 	return head;
  283. }
  284. Node* delete_iter(Node* head, int pos){
  285. 	//Take explicit care of deletion @head
  286. 	if(pos == 1){
  287. 		Node* newHead = head->next;
  288. 		head->next = null;
  289. 		delete head;
  290. 		return newHead;
  291. 	}
  292.  
  293. 	//Otherwise launch the traversal module, run a loop til pos-2 times
  294. 	Node* current = head;
  295. 	int count = 0;
  296. 	while(count < pos-2 and current != null){
  297. 		current = current->next;
  298. 		count++;
  299. 	}
  300.  
  301. 	//Now you're @the previous node to be deleted
  302. 	//do ya thing!
  303. 	//But safety check first! (i.e. you haven't come out of the traversal loop because current ran out or currently you're at the last node)
  304. 	if(current == null or current->next == null) return head;
  305.  
  306. 	Node* temp = current->next;
  307. 	current->next = current->next->next;
  308. 	temp->next = null; //crucial
  309. 	delete temp;
  310.  
  311.  
  312. 	return head;
  313. }
  314.  
  315.  
  316. Node* skipMdeleteN(Node* head, int M, int N){
  317.     //If M is 0, we delete all nodes, so return NULL
  318.     if(M == 0 || head == NULL) return NULL;
  319.  
  320.     //If N is 0, we keep all nodes, so return the original head
  321.     if(N == 0) return head;
  322.  
  323.     Node* currentNode = head; // Pointer to traverse the linked list
  324.     Node* temp = NULL; // Will track the last retained node after skipping M nodes
  325.  
  326.     while(currentNode != NULL) {
  327.         int take = 0, skip = 0;
  328.  
  329.         // **Step 1: Skip (Retain) M Nodes**
  330.         while(currentNode != NULL && take < M){
  331.             if(temp == NULL){
  332.                 temp = currentNode; //Initialize temp to track the first retained node
  333.             }else{
  334.                 temp->next = currentNode; //Ensure proper linkage
  335.                 temp = currentNode;
  336.             }
  337.             currentNode = currentNode->next;
  338.             take++;
  339.         }
  340.  
  341.         // **Step 2: Delete Next N Nodes**
  342.         Node* toBeDeleted = currentNode;
  343.         while(toBeDeleted != NULL && skip < N){
  344.             Node* nextNode = toBeDeleted->next; //Save reference to next node
  345.             toBeDeleted->next = NULL;  //Important: Disconnect the node before deleting
  346.             delete toBeDeleted; //Free memory
  347.             toBeDeleted = nextNode; //Move to next node
  348.             skip++;
  349.         }
  350.  
  351.         // **Step 3: Connect Last Retained Node to Remaining List**
  352.         if(temp != NULL) temp->next = toBeDeleted;
  353.  
  354.         //Move `currentNode` to continue processing the remaining list
  355.         currentNode = toBeDeleted;
  356.     }
  357.  
  358.     return head; //Return the modified linked list
  359. }
  360.  
  361.  
  362. int main(){
  363. //	cout<<"Enter data: "<<flush;
  364. //	Node* head = takeInput();
  365. //	print_iter(head); cout<<"| length: "<<length_iter(head)<<endl;
  366.  
  367. //	//For evenAfterOdd()
  368. //	vector<int> nums1 = {1, 4, 5, 2};
  369. //	Node* head1 = createLinkedList(nums1);
  370. //	print_iter(head1); cout<<"| length: "<<length_iter(head1)<<endl;
  371. //	head1 = evenAfterOdd(head1);
  372. //	print_iter(head1); cout<<"| length: "<<length_iter(head1)<<endl;
  373. //
  374. //	cout<<endl;
  375. //	vector<int> nums2 = {1, 11, 3, 6, 8, 0, 9};
  376. //	Node* head2 = createLinkedList(nums2);
  377. //	print_iter(head2); cout<<"| length: "<<length_iter(head2)<<endl;
  378. //	head2 = evenAfterOdd(head2);
  379. //	print_iter(head2); cout<<"| length: "<<length_iter(head2)<<endl;
  380. //
  381. //	cout<<endl;
  382. //	vector<int> nums3 = {10, 20, 30, 40};
  383. //	Node* head3 = createLinkedList(nums3);
  384. //	print_iter(head3); cout<<"| length: "<<length_iter(head3)<<endl;
  385. //	head3 = evenAfterOdd(head3);
  386. //	print_iter(head3); cout<<"| length: "<<length_iter(head3)<<endl;
  387.  
  388. //	//For swapNodes()
  389. //	vector<int> nums = {1, 2, 3, 4, 5, 6, 7};
  390. //	Node* head = createLinkedList(nums);
  391. //	print_iter(head); cout<<"| length: "<<length_iter(head)<<endl;
  392. //
  393. //	//Do modifications here:
  394. //	int i = 1, j = 5;
  395. //	head = swapNodes(head, i, j);
  396. //	print_iter(head); cout<<"| length: "<<length_iter(head)<<endl;
  397.  
  398. 	vector<int> nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  399. 	Node* head = createLinkedList(nums);
  400. 	print_iter(head); cout<<"| length: "<<length_iter(head)<<endl;
  401.  
  402. //	head = reverse_iter(head);
  403. //	print_iter(head); cout<<"| length: "<<length_iter(head)<<endl;
  404. //
  405. //	head = reverse_recur(head);
  406. //	print_iter(head); cout<<"| length: "<<length_iter(head)<<endl;
  407. //
  408. //	int k = 4;
  409. //	head = kReverse(head, k);
  410. //	print_iter(head); cout<<"| length: "<<length_iter(head)<<endl;
  411.  
  412. 	int pos = 8;
  413.  
  414. //	head = delete_iter(head, pos);
  415. //	//head = delete_recur(head, pos);
  416. //	print_iter(head); cout<<"| length: "<<length_iter(head)<<endl;
  417.  
  418. 	int M = 2, N = 3;
  419. 	head = skipMdeleteN(head, M, N);
  420. 	print_iter(head); cout<<"| length: "<<length_iter(head)<<endl;
  421.  
  422. 	return 0;
  423. }
  424.  
  425.  
  426. //11 3 9 6 8 0
  427.  
  428. /*
  429. Sample Input 1: 1 4 5 2 -1
  430. Sample Output 1: 1 5 4 2
  431.  
  432. Sample Input 2: 1 11 3 6 8 0 9 -1
  433. Sample Output 2:1 11 3 9 6 8 0
  434.  
  435. Sample Input 3: 10 20 30 40 -1
  436. Sample Output 3: 10 20 30 40
  437. */
  438.  
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1 2 3 4 5 6 7 8 9 10 | length: 10
1 2 6 7 | length: 4
https://ideone.com/30QTGO
language:
C++ (gcc 8.3)
created:
23 hours 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!