Remove Nth Node From End of List medium

Problem Statement

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: []

Steps

1. Two-Pointer Approach: We'll use two pointers, fast and slow.
2. Initial Setup: Move the fast pointer n steps ahead of the slow pointer.
3. Simultaneous Movement: Move both fast and slow pointers one step at a time until fast reaches the end of the list. At this point, slow will be n nodes away from the end.
4. Node Removal: The node after slow is the nth node from the end. Remove this node by updating the next pointer of slow.
5. Edge Cases: Handle the edge cases where n is greater than or equal to the list's length (return the original head in this case) or the list is empty.

Explanation

The two-pointer approach allows us to efficiently find the nth node from the end without needing to traverse the list multiple times. The fast pointer acts as a "look-ahead" pointer, giving us the necessary distance to identify the target node for removal.

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (head == nullptr) return nullptr; // Handle empty list

        ListNode* dummy = new ListNode(0, head); // Add a dummy node to simplify edge cases
        ListNode* fast = dummy;
        ListNode* slow = dummy;

        // Move fast pointer n steps ahead
        for (int i = 0; i <= n; ++i) {
            fast = fast->next;
            if (fast == nullptr) {
                delete dummy; //if n is greater than or equal to length of list
                return head; //Return original list
            }
        }

        // Move both pointers until fast reaches the end
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }

        // Remove the nth node from the end (node after slow)
        ListNode* temp = slow->next;
        slow->next = temp->next;
        delete temp;

        return dummy->next;
    }
};

Complexity

• Time Complexity: O(L), where L is the length of the linked list. We traverse the list once using two pointers.
• Space Complexity: O(1). We use a constant amount of extra space for the pointers.