Remove Nth Node From End of List medium

Problem Statement

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:

Input: head = [1,2,3,4,5], n = 2 Output: [1,2,3,5]

Example 2:

Input: head = [1], n = 1 Output: []

Steps:

1. Two-Pointer Approach: We'll use two pointers, fast and slow.
2. Initial Setup: The fast pointer starts n nodes ahead of the slow pointer.
3. Iteration: Both pointers move forward simultaneously until the fast pointer reaches the end of the list.
4. Removal: When fast reaches the end, slow is positioned n nodes before the end. We remove the node after slow. This is the nth node from the end.
5. Edge Case Handling: Handle the case where n is 0 or greater than the list's length, and the case where the list has only one node.

Explanation:

The key insight is that when the fast pointer reaches the end, the slow pointer is precisely at the position from which we need to remove the node. The distance between fast and slow remains constant (n) throughout the iteration.

Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Handle edge case: empty list or n is invalid
        if (head == null || n <= 0) {
            return head;
        }

        // Dummy node to simplify handling removal of the head node
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode slow = dummy;
        ListNode fast = dummy;

        // Move fast pointer n steps ahead
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }

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

        // Remove the nth node from the end (node after slow)
        slow.next = slow.next.next;

        return dummy.next; 
    }
}

Complexity:

• Time Complexity: O(L), where L is the length of the linked list. We traverse the list once.
• Space Complexity: O(1). We use only a constant number of extra variables.