Ride-hailing is a favored vehicular service model where drivers can deliver convenient rides to waiting riders via responding to a road-side unit or a ride-hailing service provider. However, previous works did not consider the order-linking function where a rider Cathy waving for a ride will be matched to a driver Bob in service with rider Alice whose destination is close to the start point of Cathy. Furthermore, a malicious matching executor could collude with an appointed driver to interfere with the matching process, which causes service unfairness and has not been addressed before. To mitigate these limitations, we first propose a privacy-preserving ride-hailing scheme OLink with the verifiable order-linking property. Specifically, we adopt road network partitioning and range query to achieve basic user matching. The user matching process supports range conditions and protects users' privacy. Next, a Proof-of-Linking protocol is designed based on the zero-knowledge succinct non-interactive argument of knowledge, zero-knowledge proof, and Bloom filters to enable the driver in service to generate three consecutive proofs for linking a current order to the next rider's order in advance; the proofs will be released such that anyone can verify the proofs and matching fairness is guaranteed. Finally, we formally prove the privacy and security of OLink, and then evaluate its performance with PySNARK to demonstrate feasibility and efficiency.