Recursively Find the kth to Last Element of a Linked List

There are many ways to find the kth to last element of a singly linked list. If you know the size of the linked list, the problem would be very easy since the kth to last element is the (length – k)th element.

Assume we have no idea about the size of the linked list, what can we do?

Here provides a recursive algorithm. Let’s treat k = 0 as the last element, k = 1 as the second to last element, and so on. The idea is to recurse to the last element. Each recursive call adds 1 to the counter. The stopping condition is to reach the last node and then returns -1. Actually, the algorithm only returns one thing which is the reverse index value. The more complicated implementation would have to return the node too. Here is my simple implementation in Java:

public static int getElement(Node head, int k) {
    int length = Node.listLength(head);
    int order = length - k;
    int answer = 0;
    Node cursor = head;
    int counter = 0;
    while (cursor != null) {
        counter++;
        if (counter == order) {
            answer = cursor.getData();
        }
        cursor = cursor.getLink();
    }
    return answer;
}

Nankai Pan

Read more posts by this author.