Link to Question

MEDIUM

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

Input:

head = [1,2,3,4,5], n = 2

Output:

[1,2,3,5]

Explanation:
The 2nd node from the end is 4, so it is removed.

---

Constraints

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

---

Solution: Two Pointers

• Time Complexity: O(L), where L is the length of the list.
• Space Complexity: O(1)

C++

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode dummy(0, head);
        ListNode* first = &dummy;
        ListNode* second = &dummy;
        // Move first n+1 steps ahead
        for (int i = 0; i <= n; ++i) {
            first = first->next;
        }
        // Move both pointers until first reaches the end
        while (first) {
            first = first->next;
            second = second->next;
        }
        // Remove the nth node
        ListNode* toDelete = second->next;
        second->next = second->next->next;
        delete toDelete;
        return dummy.next;
    }
};