  In 1999, Jacobson and Lehel conjectured that for $k \geq 3$, every
$k$-regular Hamiltonian graph has cycles of at least linearly many different
lengths. This was further strengthened by Verstra\"{e}te, who asked whether the
regularity can be replaced with the weaker condition that the minimum degree is
at least $3$. Despite attention from various researchers, until now, the best
partial result towards both of these conjectures was a $\sqrt{n}$ lower bound
on the number of cycle lengths. We resolve these conjectures asymptotically, by
showing that the number of cycle lengths is at least $n^{1-o(1)}$.
