Remove Nth Node From End of List, thesarfo

Given a list and an integer n, remove the nth node from the end and return the updated head. 1 → 2 → 3 → 4 → 5, n = 2 → remove 4 → 1 → 2 → 3 → 5. (LeetCode 19)

Brute force (two passes): traverse once to count all the nodes, use the count to find the target index from the front (count - n), traverse again and stop right before that node, then skip it. If n == count, you’re deleting the first node — just return head.next.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Step 1: Get length of the list
        int length = 0;
        ListNode temp = head;
        while (temp != null) {
            length++;
            temp = temp.next;
        }

        // Step 2: Handle case where we remove the first node
        if (n == length) {
            return head.next;
        }

        // Step 3: Go to node before the one to delete
        int target = length - n;
        temp = head;
        for (int i = 1; i < target; i++) {
            temp = temp.next;
        }

        // Step 4: Remove the node
        temp.next = temp.next.next;

        return head;
    }
}

Time: O(n) (two linear passes). Space: O(1).

Optimal — one pass, two pointers: start first and second both at head, move first forward n steps, then move both together until first hits the end — at that point second sits right before the node to delete. Moving first n steps ahead creates a gap of n between the pointers, so when first hits null, second is exactly where it needs to be. Use a dummy node to smoothly handle deleting the head when n equals the list length.

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Dummy node to handle edge cases like deleting head
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode first = dummy;
        ListNode second = dummy;

        // Step 1: Move first pointer n+1 steps forward
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }

        // Step 2: Move both pointers
        while (first != null) {
            first = first.next;
            second = second.next;
        }

        // Step 3: Delete target node
        second.next = second.next.next;

        return dummy.next;
    }
}

Time: O(n), one pass. Space: O(1).