HackerEarth Reversed Linked List problem solution

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:

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}.
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.

#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;
}

coding problems solutions