namespace LeetCode.Logic;

public class LinkedListRemover
{
    /// <summary>
    /// Removes the nth node from the end of the list and returns its head.
    /// Time Complexity: O(L) where L is the length of the linked list.
    /// Space Complexity: O(1) as we only use pointers.
    /// </summary>
    public ListNode? RemoveNthFromEnd(ListNode? head, int n)
    {
        // Use a dummy node to handle edge cases like removing the head
        ListNode dummy = new ListNode(0, head);
        ListNode? fast = dummy;
        ListNode? slow = dummy;

        // Move fast pointer so that there is a gap of n nodes between slow and fast
        for (int i = 0; i <= n; i++)
        {
            fast = fast?.next;
        }

        // Move fast to the end, maintaining the gap
        while (fast != null)
        {
            fast = fast.next;
            slow = slow?.next;
        }

        // Skip the nth node from the end
        if (slow?.next != null)
        {
            slow.next = slow.next.next;
        }

        return dummy.next;
    }
}