Java O(n) Solution
public int[] constructArray(int n, int k) {\n        int[] ret = new int[n];\n        int hi = n;\n        int lo = 2;\n        ret[0] = 1;\n        boolean las
    public int[] constructArray(int n, int k) {\n        int[] ret = new int[n];\n        int hi = n;\n        int lo = 2;\n        ret[0] = 1;\n        boolean last_hi = false;\n        for (int i = 1; i < n; i++) {\n            if (k > 1) {\n                if (!last_hi){\n                    ret[i] = hi;\n                    hi --;\n                }\n                else {\n                    ret[i] = lo;\n                    lo ++;\n                }\n                last_hi = !last_hi;\n                k--;\n            }\n            else {\n                if (last_hi) {\n                    ret[i] = hi;\n                    hi--;\n                }\n                else {\n                    ret[i] = lo;\n                    lo++;\n                }\n            }\n        }\n        return ret;\n    }
[]