C O(n) solution
\nint* sortArrayByParityII(int* A, int ASize, int* returnSize)\n{\n    int *res = malloc(sizeof(int) * ASize);\n    *returnSize = ASize;\n    int *odd, *even, i
```\nint* sortArrayByParityII(int* A, int ASize, int* returnSize)\n{\n    int *res = malloc(sizeof(int) * ASize);\n    *returnSize = ASize;\n    int *odd, *even, i = 0;\n    \n    odd = res + 1;\n    even = res;\n    \n    while(i < ASize)\n    {\n        if(A[i] % 2)\n        {\n            *odd = A[i];\n            odd +=2;\n            i++;\n            \n        }\n        else\n        {\n            *even = A[i];\n            even += 2;\n            i++;\n        }\n    }\n    return res;\n}\n```
[]