Routing of Flying Ad Hoc Networks (FANETs) is more challenging than traditional Mobile Ad Hoc Networks (MANETs) due to the high mobility of Unmanned Aerial Vehicles (UAVs). Reactive protocols that adjust routing according to the location and speed of UAVs are widely researched. In this work, a more aggressive routing protocol that is not only reactive, but also predictive, is proposed. It is based on the salient fact that both the trajectory and change of speed are smooth in most cases, and the recent movement history of UAVs provides valuable information for predicting the change of network topology. Driven by this observation, a Link-stability Prediction-based Adaptive Routing (LPAR) protocol is proposed. LPAR predicts link stability over a period of time, and makes routing decisions that are expected to last for a longer duration. In case of link breakage, LPAR can switch to a greedy forwarding mode to reduce dropping packets. Evaluated with NS3 simulation, LPAR achieves better performance than several existing reactive routing protocols in terms of packet delivery ratio (PDR), end-to-end delay, and overhead by 20.58%, 15.72% and 37.22% on average.