Remove Nth Node from End of List - C++ Solution with O(n) Time Complexity

Understanding the Problem

The core challenge of this problem is to remove the nth node from the end of a singly linked list in an efficient manner. This problem is significant in various applications such as managing tasks, memory management, and more. A common pitfall is misunderstanding the position of the nth node from the end, especially in edge cases like when the list has only one node.

Approach

To solve this problem, we can use a two-pointer technique to achieve the solution in one pass. Here's a step-by-step approach:

Naive Solution

The naive solution involves two passes through the list. In the first pass, we count the total number of nodes. In the second pass, we remove the (total - n + 1)th node from the beginning. This approach is not optimal as it requires two passes.

Optimized Solution

The optimized solution uses two pointers, `fast` and `slow`. The `fast` pointer is moved n steps ahead first. Then, both `fast` and `slow` pointers are moved one step at a time until `fast` reaches the end. At this point, the `slow` pointer will be at the (n+1)th node from the end, and we can easily remove the nth node.

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

1. Initialize two pointers, `fast` and `slow`, both pointing to the head of the list.
2. Move the `fast` pointer n steps ahead.
3. If `fast` reaches the end, it means we need to remove the head node. Return `head->next`.
4. Move both `fast` and `slow` pointers one step at a time until `fast` reaches the end of the list.
5. The `slow` pointer will now be at the (n+1)th node from the end. Remove the nth node by adjusting the pointers.
6. Return the head of the modified list.

Code Implementation

#include <iostream>
using namespace std;

// 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 easily
        ListNode* dummy = new ListNode(0, head);
        ListNode* fast = dummy;
        ListNode* slow = dummy;
        
        // Move fast pointer n steps ahead
        for (int i = 0; i < n; ++i) {
            fast = fast->next;
        }
        
        // Move both pointers until fast reaches the end
        while (fast->next != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        
        // Remove the nth node from the end
        ListNode* nodeToRemove = slow->next;
        slow->next = slow->next->next;
        delete nodeToRemove;
        
        // Return the head of the modified list
        ListNode* newHead = dummy->next;
        delete dummy;
        return newHead;
    }
};

// Helper function to print the list
void printList(ListNode* head) {
    while (head != nullptr) {
        cout << head->val << " ";
        head = head->next;
    }
    cout << endl;
}

// Main function to test the solution
int main() {
    Solution solution;
    
    // Example 1
    ListNode* head1 = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5)))));
    int n1 = 2;
    ListNode* result1 = solution.removeNthFromEnd(head1, n1);
    printList(result1); // Output: 1 2 3 5
    
    // Example 2
    ListNode* head2 = new ListNode(1);
    int n2 = 1;
    ListNode* result2 = solution.removeNthFromEnd(head2, n2);
    printList(result2); // Output: (empty list)
    
    // Example 3
    ListNode* head3 = new ListNode(1, new ListNode(2));
    int n3 = 1;
    ListNode* result3 = solution.removeNthFromEnd(head3, n3);
    printList(result3); // Output: 1
    
    return 0;
}

Complexity Analysis

The time complexity of the optimized solution is O(n), where n is the number of nodes in the list. This is because we traverse the list only once. The space complexity is O(1) as we are using only a constant amount of extra space.

Edge Cases

Some potential edge cases include:

• Removing the head node when the list has only one node.
• Removing the head node when the list has multiple nodes.
• Removing the last node in the list.

Each of these cases is handled by the algorithm as described.

Testing

To test the solution comprehensively, consider the following test cases:

• List with a single node, removing the only node.
• List with multiple nodes, removing the head node.
• List with multiple nodes, removing the last node.
• List with multiple nodes, removing a middle node.

Using a variety of test cases ensures that the solution handles all possible scenarios.

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Understand the problem requirements and constraints thoroughly.
• Think about edge cases and how to handle them.
• Break down the problem into smaller steps and solve each step methodically.
• Practice similar problems to improve problem-solving skills.

Conclusion

In this blog post, we discussed how to remove the nth node from the end of a linked list efficiently using a two-pointer technique. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for improving problem-solving skills and preparing for technical interviews.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode Problem
• GeeksforGeeks Article
• Coding Ninjas Problem