  We prove that Whitehead's algorithm for solving the automorphism problem in a
fixed free group $F_k$ has strongly linear time generic-case complexity. This
is done by showing that the ``hard'' part of the algorithm terminates in linear
time on an exponentially generic set of input pairs. We then apply these
results to one-relator groups. We obtain a Mostow-type isomorphism rigidity
result for random one-relator groups: If two such groups are isomorphic then
their Cayley graphs on the \emph{given generating sets} are isometric. Although
no nontrivial examples were previously known, we prove that one-relator groups
are generically \emph{complete} groups, that is, they have trivial center and
trivial outer automorphism group. We also prove that the stabilizers of generic
elements of $F_k$ in $Aut(F_k)$ are cyclic groups generated by inner
automorphisms and that $Aut(F_k)$-orbits are uniformly small in the sense of
their growth entropy. We further prove that the number $I_k(n)$ of
\emph{isomorphism types} of $k$-generator one-relator groups with defining
relators of length $n$ satisfies \[ \frac{c_1}{n} (2k-1)^n \le I_k(n)\le
\frac{c_2}{n} (2k-1)^n, \] where $c_1=c_1(k)>0, c_2=c_2(k)>0$ are some
constants independent of $n$. Thus $I_k(n)$ grows in essentially the same
manner as the number of cyclic words of length $n$.
