In this HackerEarth Reversed Linked List problem solution, You are given a linked list that contains N integers. You have performed the following reverse operation on the list:
  1. Select all the subparts of the list that contain only even integers. For example, if the list is {1,2,8,9,12,16}, then the selected subparts will be {2,8}, {12,16}.
  2. Reverse the selected subpart such as {8,2} and {16,12}.
Now, you are required to retrieve the original list.


HackerEarth Reversed Linked List problem solution


HackerEarth Reversed Linked List problem solution.

#include<bits/stdc++.h>
#define LL long long int
#define M 1000000007
#define endl "\n"
#define eps 0.00000001
LL pow(LL a,LL b,LL m){ a%=m;LL x=1,y=a;while(b > 0){if(b%2 == 1){x=(x*y);if(x>m) x%=m;}y = (y*y);if(y>m) y%=m;b /= 2;}return x%m;}
LL gcd(LL a,LL b){if(b==0) return a; else return gcd(b,a%b);}
LL gen(LL start,LL end){LL diff = end-start;LL temp = rand()%start;return temp+diff;}
using namespace std;
int a[1001];
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
assert(n <= 1000);
for(int i = 1; i <= n; i++) {
cin >> a[i];
assert(a[i] >= 1 && a[i] <= 1000000000);
}
int i = 1;
while(i <= n) {
if(a[i] % 2 == 0) {
int st = i, et = i;
while(i <= n && a[i] % 2 == 0) {
et = i;
++i;
}
reverse(a + st , a + et + 1);
}
else{
++i;
}
}
for(int i = 1; i <= n; i++) {
cout << a[i] << " ";
}

}

Second solution

#include <bits/stdc++.h>

using namespace std;

stack<int> stk;

struct Node {
int data;
Node *next;
};

Node *ptr;
Node *head1 = NULL;
Node *head2 = NULL;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
for(int i = 0; i < n; i ++) {
int x;
cin >> x;
Node *tmp = new Node;
tmp->data = x;
tmp->next = NULL;
if(head1 == NULL) {
head1 = tmp;
ptr = tmp;
} else {
ptr->next = tmp;
ptr = ptr->next;
}
}
while(head1 != NULL) {
if(head1->data % 2 == 0) {
stk.push(head1->data);
} else {
bool flag = 1;
while(!stk.empty() || flag) {
if(stk.empty())
flag = 0;
Node *tmp = new Node;
tmp->data = flag ? stk.top() : head1->data;
tmp->next = NULL;
if(head2 == NULL) {
head2 = tmp;
ptr = tmp;
} else {
ptr->next = tmp;
ptr = ptr->next;
}
if(!stk.empty())
stk.pop();
}
}
head1 = head1->next;
}
while(!stk.empty()) {
Node *tmp = new Node;
tmp->data = stk.top();
tmp->next = NULL;
if(head2 == NULL) {
head2 = tmp;
ptr = tmp;
} else {
ptr->next = tmp;
ptr = ptr->next;
}
stk.pop();
}
while(head2 != NULL) {
cout << head2->data << ' ';
head2 = head2->next;
}
cout << '\n';
return 0;
}