19. Remove Nth Node From End of List

1. Description

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

2. Example

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]

3. Constraints

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

4. Solutions

Two Pointers

n is the number of nodes in head
Time complexity: O(n)
Space complexity: O(1)

class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        ListNode *dummy = new ListNode();
        dummy->next = head;

        ListNode *fast = dummy, *slow = dummy;
        for (int i = 0; i < n; ++i) {
            fast = fast->next;
        }

        while (fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next;
        }

        return dummy->next;
    }
};