C++ easy solution O(n)
\nclass Solution {\npublic:\n    vector <int> gen(int n) { // generator for k = n - 1 for a given n\n        vector <int> tmp;\n        int start = 1, diff = n-
```\nclass Solution {\npublic:\n    vector <int> gen(int n) { // generator for k = n - 1 for a given n\n        vector <int> tmp;\n        int start = 1, diff = n-1;\n        bool flag = true;\n        tmp.push_back(start);\n        while(diff >= 1) {\n            if(flag) {\n                start += diff;\n            } \n            else {\n                start -= diff;\n            }\n            diff--;\n            flag = !flag;\n            tmp.push_back(start);\n        }\n        return tmp;\n    }\n    vector<int> constructArray(int n, int k) {\n        vector <int> ans;\n        if(k == 1) {\n            for(int i=1;i<=n;i++) ans.push_back(i);\n            return ans;\n        }\n        else {\n            vector <int> tmp = gen(k+1);\n            for(int i=0;i<tmp.size();i++) {\n                ans.push_back(tmp[i]);\n            }\n            for(int i=k+2;i<=n;i++) {\n                ans.push_back(i);\n            }\n        }\n        return ans;\n    }\n};\n```
[]