19. Remove Nth Node From End of List

• Link: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Question

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

Follow up: Could you do this in one pass?

Approach 1: Brute Force

Intuition

• Calculate the total size

Algorithm

1. Edge case: if (head == NULL) return head
2. Declare & initialize int count = 0, ListNode* curr = head
3. Loop through LL using curr & increment count by 1 in each iteration
4. Edge case: if (count == n)
   1. Declare & initialize ListNode* toDel tohead
   2. Declare & initialize ListNode* newHead = head->next
   3. Delete toDel
   4. Return newHead
5. Calculate the index of the node to be deleted res = count - 1
6. Reinitialize curr to head
7. Loop through LL using curr
   1. Decrement res by 1
   2. Check if (res == 0) break;
   3. curr = curr->next
8. ListNode* toDel = curr->next
9. Change links curr->next = curr->next->next
10. Delete toDel
11. Return head

Code

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (head == NULL) {
            return head;
        }

        int count = 0;

        ListNode* curr = head;

        while (curr) {
            count++;
            curr = curr->next;
        }

        if (count == n) {
            ListNode* toDel = head;
            ListNode* newHead = head->next;
            delete toDel;
            return newHead;
        }

        int res = count - n;
        curr = head;

        while (curr) {
            res--;
            if (res == 0) {
                break;
            }
            curr = curr->next;
        }

        ListNode* toDel = curr->next;
        curr->next = curr->next->next;
        delete toDel;

        return head;
    }
};

Complexity Analysis

• Time Complexity: $O(2n)=O(n)$
• Space Complexity: $O(1)$

Approach 2: Optimal

Algorithm

1. Edge Case Check:
   • If the list is empty (head == NULL), return NULL.
2. Initialize Two Pointers:
   • Create two pointers, fast and slow, both initially pointing to the head.
3. Advance the fast Pointer:
   • Move the fast pointer nnn steps forward in the list.
   • If fast becomes NULL after this step, it means the nnn-th node from the end is the head. Remove the head and return head->next.
4. Move Both Pointers:
   • Simultaneously move the fast and slow pointers one step at a time until fast->next becomes NULL.
   • At this point, the slow pointer will be just before the node to be removed.
5. Delete the Node:
   • Save a reference to the node to be removed (toDel = slow->next).
   • Update slow->next to skip the node (slow->next = slow->next->next).
6. Free Memory:
   • Delete the node referenced by toDel.
7. Return the Updated List:
   • Return the head of the updated list.

Code

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if (!head) return nullptr;

        ListNode* fast = head;
        ListNode* slow = head;

        // Move fast pointer n steps ahead
        for (int i = 0; i < n; ++i) {
            fast = fast->next;
        }

        // If fast is null, the node to remove is the head
        if (!fast) {
            ListNode* toDel = head;
            head = head->next;
            delete toDel;
            return head;
        }

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

        // Remove the nth node
        ListNode* toDel = slow->next;
        slow->next = slow->next->next;
        delete toDel;

        return head;
    }
};

Complexity Analysis

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