Sobes.tech
Junior — Middle

How can you determine the element located at a position offset by k from the end of a singly linked list?

sobes.tech AI

Answer from AI

To find the element that is positioned k places from the end of a singly linked list, you can use two pointers (the two-pointer technique):

  1. Initialize two pointers fast and slow at the beginning of the list.
  2. Move the fast pointer k positions ahead.
  3. Then, simultaneously move both pointers (fast and slow) one node at a time until fast reaches the end of the list.
  4. At this point, the slow pointer will be pointing to the desired element.

Example in C#:

class Node {
    public int Value;
    public Node Next;
}

Node FindKthFromEnd(Node head, int k) {
    Node fast = head;
    Node slow = head;
    
    for (int i = 0; i < k; i++) {
        if (fast == null) return null; // k is greater than the length of the list
        fast = fast.Next;
    }
    
    while (fast != null) {
        fast = fast.Next;
        slow = slow.Next;
    }
    
    return slow;
}

This method is efficient because it requires only one pass through the list.