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):
- Initialize two pointers
fastandslowat the beginning of the list. - Move the
fastpointer k positions ahead. - Then, simultaneously move both pointers (
fastandslow) one node at a time untilfastreaches the end of the list. - At this point, the
slowpointer 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.