Determining if a list contains two numbers whose difference is less than k
Let $f(x) = \lfloor x/k \rfloor$. Create a hash table which stores $f(x_1),\ldots,f(x_n)$; furthermore, for each $y \in \{f(x_1),\ldots,f(x_n)\}$, count how many elements map to $y$, and what is the minimal element mapping to $y$.

If any of the cells contains more than one element, then these two elements are at a distance of less than $k$. Otherwise, go over all elements, and for each $x_i$, compare $x_i$ to the minimal element mapping to $f(x_i)+1$, checking whether the two elements are at distance less than $k$. If no elements at distance less than $k$ have been found in this way, then no such elements exist.