I have to design a nondeterministic one tape Turing machine that accepts only non-palindromes in $O(n \log n)$ time.

My best shot was only in $O(n^2)$ time. How can I use the properties of NTM on a single tape to find a faster solution?