Can you find the kth to last element of a singly linked list?

Finding the kth to last element of a singly linked list is a common question in coding interviews. The key here is to observe that we do not have a direct access to the end of the linked list unless we traverse it once. With this observation, we can use the technique of maintaining two pointers that each starts at the head of the list. We move one pointer k steps forwards first, then we move both pointers at the same speed until the first pointer reaches the end. At that point, the second pointer will point to the kth to last element.

Here is a Python implementation of the algorithm:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


def find_kth_to_last(head, k):
    p1 = head
    p2 = head

    # Move p1 k nodes into the list
    for i in range(k):
        if p1 is None: return None  # If k > length of the list
        p1 = p1.next

    # Move p1 to the end, maintaining the gap
    while p1:
        p1 = p1.next
        p2 = p2.next

    # Now, p2 points to kth to last element
    return p2.val

In this sample code, the linked list is represented by a ‘ListNode‘ where ‘val‘ is the value of the node and ‘next‘ is a pointer to the next node.

The function ‘find_kth_to_last(head, k)‘ is expected to return the kth to last element of the linked list with ‘head‘ as the head node. If the length of the list is less than ‘k‘, it returns ‘None‘.

The time complexity of this algorithm is O(n) where n is the length of the list, because we are traversing the list only once. The space complexity is O(1), because we are using a fixed amount of space to store the two pointers.

However, it is important to note that in a real interview, you need to validate the input arguments (e.g., whether the head is ‘None‘ and whether ‘k‘ is non-negative) and discuss edge cases with the interviewer.