Problem: Kth to Last Element in Linked List

Another classic linked list problem is finding the kth to last element.

So consider this linked list:

          ┌───┐     ┌───┐     ┌───┐     ┌───┐
head ───▶ │ 8 │ ──▶ │ 7 │ ──▶ │ 5 │ ──▶ │ 9 │ ──▶ null
          └───┘     └───┘     └───┘     └───┘

Here are some examples of what the method should return:

  • If k = 0, it should return the last element, which is the item with value 9.
  • If k = 1, it should return the second to last element, which is the item with value 5.
  • If k = 2, it should return the third to last element, which is the item with value 7.
  • If k = 3, it should return the fourth to last element, which is the item with value 8.
  • If k = 4 or any larger number, it should return null, since there is no such element.

The signature of the method in Java might look like this:

public static ListItem kthToLast(ListItem head, int k) {
  // Your implementation goes here
}

Where ListItem is the class we defined earlier in this chapter.

Let’s think of some special or edge cases as well:

  • If the input list is empty (i.e., head is null), there are no elements, so the method should return null for any value of k.
  • If k is negative, it is out of bounds, so the method should return null.
  • If k is greater than or equal to the length of the list, it is also out of bounds, so the method should return null (as in the case of k = 4 in the example above).

As with the earlier problems, we want to solve this with auxiliary space and with a single pass through the list.