How to find the Nth element of a Linked List?

This is a very popular interview question. The idea is to find the Nth element from the tail but in only one pass. Without repeated iteration and visiting nodes multiple times.

The algorithm that we are going to use to solve this uses two pointers, fast and slow. The slow pointer starts when the fast pointer reaches the Nth or Kth node.
For example, to find the 3rd element from the last, the second or slow pointer should start when the first pointer (fast) has reached the third element.

After that, both pointers will keep moving one step at a time until the fast pointer points to null, which signals the end of the linked list.
At this time, the second or the slow pointer is pointing to the 3rd or Nth node from the last.

Here is the implementation of the above logic:

public Node<T> findNthNode(int n) {
    Node<T> fast = head;
    Node<T> slow = head;
    int counter = 0;

    // move only fast
    while (fast.next != null && counter <= n) {
        fast = fast.next;
        counter++;
    }}

    // now move both fast and slow one step
    while (fast.next != null) {
        fast = fast.next;
        slow = slow.next;
    }
    
    return slow;
}

So we first move only the fast node and we keep a count of steps using the counter variable. 
When we get to the end of the list OR counter becomes greater than n, we stop that loop and initiate another one where we move both fast and slow pointer one step.

This could also be written a bit simpler:

public Node<T> findNthNode(int n) {
    Node<T> fast = head;
    Node<T> slow = head;
    int start = 1;

    while (fast.next != null) {
        fast = fast.next;
        start++;

        if (start > n) {
            slow = slow.next;
        }
    }

    return slow;
}

Here, we did everything in only one loop.

The time complexity of finding the Nth node from the tail in the Linked list is O(n) - since we are iterating through the list and visiting each node with the fast pointer.

The space complexity is O(1).