Solution: A Fixed Gap Between Two Pointers

If we knew how many items are in the list, we could find the kth-to-last element by calculating the index of that element from the start and then traversing to it. Imagine if we have a method like this:

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

Then we can implement it with a for loop:

ListItem current = head;
for (int i = 0; i < length - k - 1; i++) {
  current = current.next;
}
return current;

We just traverse to the item at index length - k - 1 and return it. The problem is that we do not know the length of the list. Okay, we could first traverse the list to count how many items there are, and then traverse a second time to get to the target item.

int length = 0;
ListItem current = head;
while (current != null) {
  length++;
  current = current.next;
}
// now we know the length, we can find the target index

But that is two passes through the list, which is not ideal. We want to solve this in a single pass.

The two-pointer technique has worked on the previous problems, so let’s try to apply it to the kth-to-last problem.

What if we let the current pointer traverse the list, and at the same time we have another pointer, let’s call it kth, that starts moving only after current is more than k steps ahead? Then when current reaches the end of the list, kth will be at the kth-to-last element. For example, if k = 0, kth waits one step before it starts moving, so when current reaches null, kth is on the last node. Let’s write that out:

public static ListItem kthToLast(ListItem head, int k) {
  if (k < 0) {
    return null;
  }

  ListItem current = head;
  ListItem kth = head;
  int steps = 0;
  while (current != null) {
    current = current.next;
    if (steps > k) {
      kth = kth.next;
    }
    steps++;
  }
  return steps > k ? kth : null;  // if k is out of bounds, return null
}

Let’s trace it on the list 8 → 7 → 5 → 9 with k = 1, which should return 5, the second-to-last item. The steps > k guard keeps kth at the head until current moves k + 1 = 2 steps ahead, which creates a fixed gap:

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

From here the two pointers move together, one node per step, so the gap never changes:

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

One more step and current moves off the end onto null. The loop stops, and kth is left at 5:

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

Once current has moved k + 1 steps ahead, the gap stays at k + 1 positions for the rest of the loop. So when current steps off the end onto null, kth is k + 1 positions back from there. That is index length - k - 1, which is the same index the two-pass version traverses to.

Does this handle the edge cases correctly?

• If k is greater than or equal to the length of the list, then steps will never become greater than k. In that case, there is no kth-to-last item, so we should return null, which is what the condition steps > k ? kth : null does.

• If k is negative, it is out of bounds, so we return null immediately.

• If the list is empty (head is null), then current will be null from the start, steps will stay 0, and we will return null, which is correct.

This implementation is $O(n)$ in time, since we traverse the list once. It is $O(1)$ in auxiliary space, since we only use a constant amount of extra space for the pointers and the step counter.