How would you get the nth node from the tail in a singly linked list (in one traverse)?

Question

So I got this question from an exam.

How would you get the nth node from the tail in a singly linked list?

Each Node has a value and a next (which is a pointer to the next value). We are given this:

getNodeFromTail(Node head, int x) {

}

So the way I did it is to find the length of the list by traversing it once. Then going again to get the (length - x) node. So in total, 2 traversals.

getNodeFromTail(Node head, int x) {
    int length = 0;
    Node headdupe = head;
    while (headdupe.next != NULL) {
         headdupe = headdupe.next;
         length++;
    }
    int a = length--;
    for (int y = 0; y < a; y++) {
         head = head.next;
    }
    return head;
}

This is right, but there is also a bonus question that is asking whether we can do the same thing, but only traversing it once. I couldn't think of it during the exam, but after I thought of one way, but I'm not too sure about it.

I could make an ArrayList of length x. Then every time I run the while-loop, I would add an element to the top of the array, cascade down and kick off the last element of the array. Then when the head hits null, return the node at the array[x-1].

Is this right? Is there a better solution?

Answer 1

1. Make 2 pointers to the first node
2. Advance one pointer by x
3. Advance both pointers side by side until the one further in the list hits the end.
4. Your pointer further back points to the xth last element.