Detect cycles of odd total weight in a graph with {0,1}-weighted edges
Construct the edge-vertex incidence matrix: rows correspond to edges, columns to vertices, and there is a $1$ if the edge is incident to the vertex. Add another columns full of $1$'s. You want to know whether there is a subset of the rows summing to the vector $0,\ldots,0,1$ (modulo 2). You can find out using Gaussian elimination, in polynomial time.

What is happening here? Let us consider the original edge-vertex incidence matrix. Rows corresponding to cycles sum to zero, since each vertex appears in exactly two edges. Conversely, if we have a set of rows summing to zero, then the degree of each vertex is even. Starting at an arbitrary edge, we can trace a walk that will eventually close onto itself. We remove the corresponding cycle (which need not contain the original edge), and continue. In this way, we see that a set of rows summing to zero correspond to an edge-disjoint union of cycles.

By adding an additional $1$ column to the matrix, we are tracing the parity of the cycle. An odd cycles sums up to the vector $0,\ldots,0,1$. Conversely, if a set of rows sums to $0,\ldots,0,1$, then it corresponds to a set of cycles whose total length is odd, so one of the cycles is odd.

Finally, finding whether a vector is in the row space of the matrix is a standard problem in linear algebra, which can be solved using Gaussian elimination and related algorithms.