19. Remove Nth Node from End of List.md

19. Remove Nth Node from End of List | C++ Solution | Optimized Approach | Brute Force / Naive Approach | Two Pointers Approach

Intuition

The problem is asking to remove the nth node from the end of the list. The first thought that comes to mind is to use a two-pointer technique where the first pointer advances the list by n+1 steps from the beginning, while the second pointer starts from the beginning of the list.

Approach

1. Brute Force / Naive Approach: We first count the number of nodes in the list. Then we iterate over the list again to find the node to be deleted. We then delete the node and return the head. If the list has only one node, we return NULL. If the node to be deleted is the head, we return head->next. Otherwise, we iterate over the list to find the node to be deleted and delete it.

2. Two Pointers: We use two pointers, fast and slow. We first move the fast pointer n steps ahead. If this pointer becomes null, that means we are required to delete the head node, so we return head->next. If not, we move both fast and slow pointers simultaneously until fast reaches the end. The slow pointer will be pointing at the previous node of the node to be deleted. We then delete the node and return the head.

Complexity

• Brute Force / Naive Approach:

  • Time complexity: $O(n)$ because we make two passes through the list, so precisely $O(2n)$.
  • Space complexity: $O(1)$ because we don't use any additional space.

• Two Pointers:

  • Time complexity: $O(n)$ because we make one pass through the list.
  • Space complexity: $O(1)$ because we don't use any additional space.

Code

1. Brute Force / Naive Approach

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* curr = head;
        int s = 0;
        while (curr != NULL) {
            s++;
            curr = curr->next;
        }

        curr = head;

        if (s == 1) {
            delete head;
            return NULL;
        } else if (s == n) {
            head = curr->next;
            delete curr;
        } else {
            int count = 1;
            while (curr != NULL) {
                if (s - n == count)
                    break;
                count++;
                curr = curr->next;
            }
            ListNode* delNode = curr->next;
            curr->next = curr->next->next;
            delete delNode;
        }

        return head;
    }
};

2. Two Pointers

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* fast = head;
        ListNode* slow = head;

        for (int i = 0; i < n; i++) {
            fast = fast->next;
        }

        if (fast == NULL) {
            return head->next;
        }

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

        ListNode* delNode = slow->next;
        slow->next = slow->next->next;
        delete delNode;

        return head;
    }
};