As a forerunner in 5G technologies, Narrowband Internet of Things (NB-IoT) will be inevitably coexisting with the legacy Long-Term Evolution (LTE) system. Thus, it is imperative for NB-IoT to mitigate LTE interference. By virtue of the strong temporal correlation of the NB-IoT signal, this letter develops a sparsity adaptive algorithm to recover the NB-IoT signal from legacy LTE interference, by combining $K$-means clustering and sparsity adaptive matching pursuit (SAMP). In particular, the support of the NB-IoT signal is first estimated coarsely by $K$-means clustering and SAMP algorithm without sparsity limitation. Then, the estimated support is refined by a repeat mechanism. Simulation results demonstrate the effectiveness of the developed algorithm in terms of recovery probability and bit error rate, compared with competing algorithms.