Problem Description

You are given the beginning of a linked list head, and an integer n.

Remove the nth node from the end of the list and return the beginning of the list.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Approach

Use the “fast and slow pointer” approach with a dummy node.

1. Create a prev dummy node pointing to head to handle cases where the head itself needs to be removed.
2. Initialize both slow and fast pointers at the prev dummy node.
3. Advance the fast pointer by n + 1 steps. By doing this, the gap between slow and fast becomes n + 1.
4. Move both slow and fast pointers one step at a time until fast reaches null (the end of the list). At this point, the slow pointer will be exactly at the node before the target node to be deleted.
5. Skip the target node by updating slow.next to slow.next.next.
6. Return prev.next as the new head of the list.

Solution

/**
 * 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) {
        ListNode prev = new ListNode(0, head);
        ListNode slow = prev;
        ListNode fast = prev;
        int t = n;
        while(t>=0){
            fast = fast.next;
            t--;
        }
        while(fast != null){
            slow = slow.next;
            fast = fast.next;
        }

        slow.next= slow.next.next;
        return prev.next;


    }
}