Kth to Last Element in Linked List #

Solution: Two Pointers Approach #

public static ListNode kthToLast(ListNode head, int k) {
    // Handle edge cases
    if (head == null || k <= 0) {
        return null;
    }

    // Initialize two pointers
    ListNode fast = head;
    ListNode slow = head;

    // Move fast pointer k steps ahead
    for (int i = 0; i < k; i++) {
        if (fast == null) {
            // k is larger than list length
            return null;
        }
        fast = fast.next;
    }

    // Move both pointers until fast reaches the end
    while (fast != null) {
        fast = fast.next;
        slow = slow.next;
    }

    // slow is now pointing to kth to last element
    return slow;
}

Algorithm Explanation #

Two Pointers Strategy #

The key insight is to maintain a gap of k nodes between two pointers:

1. Setup phase: Move the fast pointer k steps ahead of the slow pointer
2. Traverse phase: Move both pointers together until fast reaches the end
3. Result: When fast is null, slow points to the kth to last element

Why This Works #

Gap Maintenance: By keeping exactly k nodes between the pointers:

• When fast reaches the end (null), slow is exactly k positions from the end
• This works because we've maintained the k-node gap throughout the traversal

Step-by-Step Trace #

Example: head = [1,2,3,4,5], k = 2

Initial: fast = slow = head (node 1)
List: 1 -> 2 -> 3 -> 4 -> 5 -> null

Setup Phase (move fast k=2 steps ahead):
Step 1: fast moves to node 2
        slow: 1, fast: 2
Step 2: fast moves to node 3
        slow: 1, fast: 3

Gap established: 2 nodes between slow and fast

Traverse Phase (move both until fast reaches end):
Step 3: slow: 2, fast: 4
Step 4: slow: 3, fast: 5
Step 5: slow: 4, fast: null (end reached)

Result: slow points to node 4 (2nd to last element)

Example: head = [1,2,3], k = 5 (k > length)

Initial: fast = slow = head (node 1)

Setup Phase (try to move fast k=5 steps ahead):
Step 1: fast moves to node 2
Step 2: fast moves to node 3
Step 3: fast moves to null
Step 4: fast is null, can't move further
Step 5: fast is null, can't move further

Since fast became null before completing k steps,
k is larger than list length → return null

Alternative Approach: Count-Then-Find Strategy #

This approach uses a more straightforward strategy that might be easier to understand:

public static ListNode kthToLastTwoPass(ListNode head, int k) {
    // First pass: count total length
    int length = 0;
    ListNode current = head;
    while (current != null) {
        length++;
        current = current.next;
    }

    // Check if k is valid
    if (k > length || k <= 0) {
        return null;
    }

    // Second pass: find (length - k)th node (0-indexed)
    // If length=5 and k=2, we want the element at position 5-2=3 (0-indexed)
    current = head;
    for (int i = 0; i < length - k; i++) {
        current = current.next;
    }

    return current;
}

Why the two-pointer approach is better: While this approach is easier to understand (count first, then find), it requires going through the list twice. The two-pointer approach is more elegant because it solves the problem in a single pass through the list.

Performance Analysis #

Two Pointers Approach:

• Time Efficiency: Linear performance - single pass through the list
  • At most n + k operations where n is list length
  • Each node visited at most once
• Memory Efficiency: Very efficient memory usage
  • Only uses two pointer variables
  • No additional data structures needed

Two-Pass Approach:

• Time Efficiency: Linear performance - two passes through the list
  • First pass: count length (n operations)
  • Second pass: find target node (n-k operations)
• Memory Efficiency: Very efficient memory usage
  • Only uses basic variables

Key Insights #

This problem reinforces:

• Two pointers technique for linked list problems
• Gap maintenance between pointers for relative positioning
• Edge case handling (empty list, k too large)
• Single-pass algorithms for efficiency
• Pointer manipulation in linked structures

Common Mistakes #

1. Off-by-one errors: Confusing 0-indexed vs 1-indexed counting
2. Null pointer exceptions: Not checking if fast pointer becomes null during setup
3. Wrong gap size: Not maintaining exactly k nodes between pointers
4. Edge case oversight: Not handling empty list or invalid k values
5. Incorrect termination: Wrong condition for when to stop moving pointers

Edge Cases #

1. Empty list: head = null → return null
2. k too large: k > list length → return null
3. k equals list length: Should return first element
4. Single element list: Works correctly with k=1
5. k = 1: Should return last element

Visual Representation #

Two pointers with gap of k=3:

Initial Setup (after moving fast k steps):
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
     ↑              ↑
   slow           fast
   (gap of 3 nodes)

After traversing to end:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> null
                    ↑              ↑
                  slow           fast
                (3rd to last)    (null)