A scheme for generating Cluster state with the quantum non-demolition polarization parity gate was presented based on weak cross-Kerr nonlinearity and linear-optics elements. The nonlinearity of cross-Kerr medium was introduced in the present scheme in order to achieve effectively the interaction between photons and achieve the desired photon entangled state. The success probability and the perfect fidelity for generating a cluster state could be enhanced due to introducing the nonlinearity of cross-Kerr and quantum non-demolition measurement on the coherence probe modes. The distinct feature of the present scheme is its preparation for a polarization four-photon cluster state with near unity success probability and near perfect fidelity. Furthermore, the cluster state of 3N+1 photons could be obtained with the help of linear optical elements based on the present scheme.