Remove Nth Node From End of List: 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: []

Example 3:

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

Constraints:

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

Try this Problem on your own or check similar problems:

1. Swapping Nodes in a Linked List
2. Delete the Middle Node of a Linked List

Solution:

public ListNode removeNthFromEnd(ListNode head, int n) {
    ListNode dummy = new ListNode(-1, head);
    ListNode slow = dummy, fast = dummy;

    while(n-->0){
        fast = fast.next;
    }
    while(fast.next != null){
        slow = slow.next;
        fast = fast.next;
    }

    slow.next = slow.next.next;
    return dummy.next;
}

Time/Space Complexity:

• Time Complexity: O(n)
• Space Complexity: O(1)

Explanation:

We solve this problem using fast and slow pointers, if we move the fast pointer n nodes, and then move the fast and slow pointer simultaneously until we reach the end of the list (last element not the node null after it) we would make a difference of n nodes between slow and fast pointer. So the slow pointer would be pointing to the (n-1)th node (because we started from dummy node) from the end of the linked list which we have to remove. How do we remove the nth node? Well we just make the current node slow is pointing to, point to the element after the nth element with slow.next = slow.next.next; (basically skipping the nth element). Since the dummy.next is pointing to the head of the list with nth element from the end removed we just return it as the result.