LeetCode 19 Solution - Remove Nth Node From End of List

Problem Statement (LeetCode 19)

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]

---

Optimal Approach: Two Pointers (Fast and Slow Pointers)

Intuition

To solve this problem efficiently, we can use the two pointers technique:

1. Fast Pointer: Move the fast pointer n steps ahead.
2. Slow Pointer: After moving the fast pointer, move both fast and slow pointers simultaneously until the fast pointer reaches the end of the list. The slow pointer will be just before the node to be deleted.

By using the two pointers, we avoid having to traverse the list multiple times or storing the nodes, which makes the solution both time-efficient and space-efficient.

---

LeetCode-Compatible C++ 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) {
        // Create a dummy node to handle edge cases like removing the head node
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        
        ListNode* fast = dummy;
        ListNode* slow = dummy;
        
        // Move the fast pointer n steps ahead
        for (int i = 0; i <= n; ++i) {
            fast = fast->next;
        }
        
        // Move both fast and slow pointers until fast reaches the end
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        
        // Now slow is at the node just before the node to be deleted
        slow->next = slow->next->next;
        
        // Return the new head
        return dummy->next;
    }
};

---

Step-by-Step Explanation of Code

1. Dummy Node:
   A dummy node is created and points to the head of the list. This helps in handling edge cases such as removing the head node without special treatment.

2. Fast and Slow Pointers:
   Both the fast and slow pointers start at the dummy node. The fast pointer is moved n steps ahead of the slow pointer.

3. Moving Both Pointers:
   After moving the fast pointer n steps ahead, both the fast and slow pointers are moved one step at a time until the fast pointer reaches the end of the list.

4. Remove the Node:
   Once the fast pointer reaches the end, the slow pointer is just before the node that needs to be removed. The slow->next pointer is updated to skip the node to be removed, effectively removing it from the list.

5. Return the New Head:
   Finally, the new head of the list (which might be different if the head node was removed) is returned by accessing dummy->next.

---

Dry Run with Example

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

1. Initialization:
   The dummy node is created: dummy -> 1 -> 2 -> 3 -> 4 -> 5.
   fast and slow both point to dummy.

2. Move fast Pointer:
   Move fast pointer n steps ahead (2 steps):
   fast points to node 3 (after moving two steps).

3. Move Both Pointers:
   Move both fast and slow one step at a time:

   • fast moves to 4, slow moves to 1.
   • fast moves to 5, slow moves to 2.
   • fast moves to nullptr, slow moves to 3.

4. Remove the Node:
   slow is now pointing to node 3. We remove slow->next, which is node 4.

5. Return Result:
   The new head of the list is 1 -> 2 -> 3 -> 5.

Output: [1, 2, 3, 5]

---

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Traverse List Twice)	O(n)	O(1)	Requires two passes over the list.
Sorting	O(n log n)	O(1)	Sorting is not appropriate for linked lists and doesn't preserve original order.
Dynamic Programming (DP)	O(n)	O(n)	Overkill for this problem since we don't need to store previous states.
Two Pointers (Optimal)	O(n)	O(1)	Most efficient and optimal solution for this problem.

---

Why Two Pointers is the Best

• Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list once.
• Space Complexity: O(1), since we only use a constant amount of extra space for the pointers.
• Optimal Solution: This approach minimizes time complexity and avoids the need for extra space.

---

Complexity Analysis

• Time Complexity: O(n)
  We only need to traverse the linked list once using the two pointers.

• Space Complexity: O(1)
  We use only a constant amount of space, aside from the input and output.

---

Conclusion

✅ Best Approach: Two Pointers
✅ Time Complexity: O(n)
✅ Space Complexity: O(1)
✅ Optimal Solution for Linked List Manipulation

Recommended Problems for Practice

1. Remove Linked List Elements (LeetCode 203)
2. Reverse Linked List (LeetCode 206)
3. Merge Two Sorted Lists (LeetCode 21)

🚀 Master the Two Pointers Technique for Efficient Linked List Operations!