# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    '''
    Time Complexity: O(n)
    Space Complexity: O(1)
    where, n is the number of nodes in the linked list.
    NOTE: Using a dummy node simplifies the edge cases, such as when the head node needs to be removed.
    '''
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        dummy = ListNode()
        dummy.next = head
        slow, fast = dummy, head
        for _ in range(n):
            fast = fast.next
        
        while fast:
            fast = fast.next
            slow = slow.next
        
        deletedNode = slow.next
        slow.next = None
        if deletedNode:
            slow.next = deletedNode.next
            deletedNode.next = None
        
        return dummy.next


class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random

/**
 * 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; }
 * }
 */
public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(0, head);
    ListNode end = dummy;
    ListNode nNode = dummy;
    for (int i=0; i<=n; i++) {
        end = end.next;
    }
    while (end != null) {
        nNode = nNode.next;
        end = end.next;
    }
    nNode.next = nNode.next.next;
    return dummy.next;
}