Perfect matching in a bipartite regular graph in linear time
There is a classical linear time algorithm of Gabow and Kariv.

The first step is to find an Eulerian tour. You do this by starting at an arbitrary vertex and following an arbitrary path until you close a cycle. If you're not back where you started, you continue following an arbitrary path until closing a cycle, and so on. If you are back where you started, you find another vertex which has unused edges, and start a new walk from there. Eventually, you will have decomposed all edges into cycles. If you're careful, you can implement this algorithm in $O(n)$; see Wikipedia for hints.

Since the graph is bipartite, all cycles have even length. Remove from each cycle every other edge to obtain a bipartite 2-regular graph. Now repeat the same process to obtain a perfect matching.

This algorithm works more generally for $d$-regular graphs whenever $d$ is a power of 2. It runs in time $O(m)$ even for non-constant $d$ (here $m$ is the number of edges). Cole, Ost, and Shirra devised an $O(m)$ time algorithm for any value of $d$, Alon devised a simple $\tilde{O}(m)$ algorithm for the same problem, and Goel, Kapralov and Khanna gave a randomized $\tilde{O}(n)$ algorithm in the same setting.