kth to last

Implement an algorithm to find the kth to last element of a singly linked list.

Solution

We will use two pointers to iterate through the linked list, and stagger the pointers by a distance of k.

def find_k_value(linked_list, k):
  first = linked_list.head
  second = linked_list.head

  for i in range(k):
    first = first.next
  

  while first:
    first = first.next
    second = second.next

  return second.value

The solution will iterate through the linked list once, so the time complexity is \(O(n)\).