  Finding a Hamiltonian cycle in a given graph is computationally challenging,
and in general remains so even when one is further given one Hamiltonian cycle
in the graph and asked to find another. In fact, no significantly faster
algorithms are known for finding another Hamiltonian cycle than for finding a
first one even in the setting where another Hamiltonian cycle is structurally
guaranteed to exist, such as for odd-degree graphs. We identify a graph class
-- the bipartite Pfaffian graphs of minimum degree three -- where it is
NP-complete to decide whether a given graph in the class is Hamiltonian, but
when presented with a Hamiltonian cycle as part of the input, another
Hamiltonian cycle can be found efficiently.
  We prove that Thomason's lollipop method~[Ann.~Discrete Math.,~1978], a
well-known algorithm for finding another Hamiltonian cycle, runs in a linear
number of steps in cubic bipartite Pfaffian graphs. This was conjectured for
cubic bipartite planar graphs by Haddadan [MSc~thesis,~Waterloo,~2015]; in
contrast, examples are known of both cubic bipartite graphs and cubic planar
graphs where the lollipop method takes exponential time.
  Beyond the lollipop method, we address a slightly more general graph class
and present two algorithms, one running in linear-time and one operating in
logarithmic space, that take as input (i) a bipartite Pfaffian graph $G$ of
minimum degree three, (ii) a Hamiltonian cycle $H$ in $G$, and (iii) an edge
$e$ in $H$, and output at least three other Hamiltonian cycles through the edge
$e$ in $G$.
  We also present further improved algorithms for finding optimal traveling
salesperson tours and counting Hamiltonian cycles in bipartite planar graphs
with running times that are not known to hold in general planar graphs.
