LeetCode 905. Sort Array By Parity

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted. 

class Solution(object):
    def sortArrayByParity(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        odd_list = []
        even_list = []
        final_list = []
        A_length = len(A)
        for i in range(A_length):
            if A[i] % 2 == 0:
                even_list.append(A[i])
            else:
                odd_list.append(A[i])
                
        final_list = even_list + odd_list
        return final_list

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        vector<int> final_list(A.size());
        int count_odd = 0;
        int count_even = 0;
        for(int i = 0; i < A.size(); i++){
            if(A[i] % 2 == 0){
                count_even++;
            }
            else{
                count_odd++;
            }
        }
        vector<int> odd_list(count_odd);
        vector<int> even_list(count_even);
        int odd = 0;
        int even = 0;
        for(int i = 0; i < A.size(); i++){
            if(A[i] % 2 == 0){
                even_list[even++] = A[i];
            }
            else{
                odd_list[odd++] = A[i];
            }
        }
        final_list = even_list;
        final_list.insert(final_list.end(),odd_list.begin(),odd_list.end());
        return final_list;
    }
};