Complexity of the Hamiltonian Subcycle problem
Some standard terminology:


A set of cycles that spans all nodes is called a cycle cover (or "vertex-disjoint cycle cover").
Cycle covers and perfect matchings are special cases of graph factors: cycle covers are 2-factors (spanning 2-regular subgraphs) and perfect matchings are 1-factors (spanning 1-regular subgraphs).


Polynomial-time algorithms:


As Tsuyoshi pointed out, finding a cycle cover in a given graph can be reduced to the problem of finding a perfect matching in a bipartite graph.
More generally, Tutte (1954) shows the following: for any graph $G$ and any integer $f$ it is possible to construct a graph $G'$ such that $G'$ has a 1-factor (perfect matching) if and only if $G$ has an $f$-factor.


As is well known, there are polynomial-time algorithms for perfect matchings.