Low earth orbit (LEO) satellite communication based on 3GPP standard is seen as a promising solution to rolling out communication services in areas without terrestrial base stations. However, due to the fast movement of satellites and large beam footprint size, the existing 5G timing advance (TA) estimation mechanism cannot be directly applied when global navigation satellite system is unavailable. In this article, an enhanced TA estimation approach is proposed for LEO satellite communication networks. Specifically, a user-side time-frequency pre-compensation method is introduced at first, which leverages frequency offset measurement on synchronization signal blocks broadcasted by satellites in initial cell search phase. For the random access phase, the upper bound of inter-preamble interference incurred by partial-period cross-correlation operations is derived for a preamble format advised by 3GPP, and it is shown that the interference level is closely related to the square of the number of such operations. Inspired by this result, a cyclic prefix free preamble format is further designed, which features extended guard time, differential power allocation and flexible preamble structure. Numerical results show that our proposal can reduce the missed detection rate of preamble within a beam. Particularly, the missed detection rates of preamble under 32, 48, and 64 users are lower than 1% when SNR = -6 dB, which is a significant improvement compared to baselines. In addition, our proposal can limit the TA estimation error of the detected users to the time length of 25 time-domain sampling points when the subcarrier spacing is 30 kHz and operation frequency is 27 GHz.