95. Find the Nth Node From the End of a Linked List

A singly linked list has n node values. Given k, print the value of the kth node counting from the end (k=1 means the last node). If k is greater than n, print -1.

Input: The first line contains an integer n. The second line contains n space-separated integers, the list's values. The third line contains k. Output: Print a single integer - the value of the kth node from the end, or -1 if k is greater than n.

1 <= n <= 10^5, 1 <= k <= 10^5

This 'maintain a fixed gap between two pointers' technique is a close cousin of the slow/fast pointer technique - both use TWO pointers moving at different paces or offsets to extract positional information in a single pass.

Find the value of the node that's k positions from the END of a linked list, without knowing the list's length in advance. Brute force: Walk the list once to count its total length n, then walk it again from the head for (n-k) steps to reach the target - this works but needs TWO full passes, when a single pass suffices. Optimised: Advancing one pointer k steps ahead first, then moving both pointers together, maintains a constant gap of exactly k nodes between them - when the lead pointer runs out of list, the trailing pointer is automatically exactly k nodes from the end, found in a SINGLE combined pass with no need to know the list's length upfront.

Traverse the linked list once, copying every value into an array, then directly index into that array at position (length - k) to read off the k-th value from the end, printing -1 if k exceeds the list's length. This is correct because an array trivially supports random access once all values are stored, but it uses extra memory proportional to the whole list just to get positional access that the original list didn't offer directly. Time: O(n) Space: O(n)

Advance a lead pointer k steps ahead from the head first (printing -1 immediately if the list runs out before that finishes), then advance both the lead pointer and a trail pointer (starting at the head) one step at a time together until the lead pointer reaches the end of the list; the trail pointer is then exactly at the k-th node from the end. This is correct because maintaining a fixed gap of k nodes between the two pointers means that when the lead pointer exhausts the list, the trail pointer has necessarily covered exactly (n - k) steps, and it accomplishes this in a single sweep through the list rather than needing to know the length beforehand. Time: O(n) Space: O(1)

Make one pass through the list to count its total length n, then, if k is within range, make a second pass starting from the head and advance exactly (n - k) steps to land on the target node. This is correct because knowing the total length up front lets the k-th-from-end position be translated directly into a from-the-front offset, and it avoids storing any extra data structure, needing only two sequential traversals instead of one traversal plus an auxiliary array. Time: O(n) Space: O(1)

1. Use two pointers, both starting at the head. 2. Advance the FIRST pointer k steps ahead, by itself. 3. Then move BOTH pointers forward together, one step at a time - when the first pointer reaches the end (null), the second pointer is exactly at the target node.

Time: O(n) - a single pass through the list. Space: O(1) - just two pointers.

k = n (asking for the head node); k greater than n (print -1); k = 1 (the last node); n = 10^5 for performance.

Be ready to handle the edge case where k is larger than the list's length (print -1) - the lead pointer running off the end of the list BEFORE the second pointer even starts moving is the signal to detect this.