There is a more economical solution for DFAs.
Suppose that $\langle Q,\Sigma,q_0,\delta,F \rangle$ is a DFA for $L$. We construct a DFA $\langle Q', \Sigma', q'_0, \delta',F' \rangle$ for $L_1$ as follows:
- $Q' = Q \times \{0,1\} \cup \{ q_{\mathit{sink}} \}$.
- $q'_0 = \langle q_0, 0 \rangle$.
- If $\delta(q,\sigma) \in F$ then $\delta'(\langle q,0 \rangle, \sigma) = \langle \delta(q,\sigma),1 \rangle$.
- If $\delta(q,\sigma) \notin F$ then $\delta'(\langle q,0 \rangle, \sigma) = q_{\mathit{sink}}$.
- $\delta'(\langle q,1 \rangle, \sigma) = \langle \delta(q,\sigma), 0 \rangle$.
- $\delta'(q_{\mathit{sink}}, \sigma) = q_{\mathit{sink}}$.
- $F' = Q \times \{0,1\}$.
What's going on here? The states $Q \times \{0,1\}$ keep track of both the state of the original automaton, and the parity of the current number of letters read. We are in one of these states as long as the condition "every odd-length prefix is in $L$" holds. If it stops holding, we move to a sink state.