Removing the Nth Node From the End of a Linked List in C++

Featured Summary: To efficiently remove the Nth node from the end of a linked list, utilize a two-pointer technique with a dummy node. Advance a fast pointer n+1 steps ahead, then iterate both fast and slow pointers simultaneously until the fast pointer reaches the end. The slow pointer will be perfectly positioned just before the target node, allowing you to bypass it in a single pass.

Understanding linked list manipulation is a critical skill for technical interviews and efficient memory management. This algorithmic problem tasks you with modifying a given linked list to delete a specific node starting from its tail end. We will explore the optimal C++ solution that achieves this in exactly one pass, ensuring a strict O(L) time complexity.

For the original problem description and competitive testing, view the Remove Nth Node From End of List challenge on LeetCode.

Problem Statement and Examples

Given the head of a linked list, you must remove the nth node from the end of the list and return its head.

Example 1: Standard Deletion

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

Example 2: Single Node Deletion

Input: head = [1], n = 1
Output: []

Example 3: Head Node Deletion

Input: head = [1,2], n = 1
Output: [1]

Deep Dive: The Two-Pointer Technique

The two-pointer technique is a fundamental algorithmic pattern used extensively in linked list and array manipulation problems. By utilizing two distinct pointers traversing the data structure at different speeds or intervals, we can solve problems that would normally require multiple iterations or auxiliary memory.

In the context of removing the Nth node from the end of a linked list, the two-pointer strategy completely eliminates the need for calculating the total list length. We maintain a strict separation of exactly n nodes between our fast and slow pointers. As the fast pointer cascades to the end of the list, the slow pointer is inherently dragged along to the exact position necessary for the deletion operation.

Space and Time Complexity Analysis

When analyzing the performance of this approach in C++, we find it to be highly optimal:

• Time Complexity: The algorithm runs in O(L) time, where L is the number of nodes within the linked list. The fast pointer traverses the list exactly one time, rendering it a pure one-pass solution.
• Space Complexity: The algorithm runs in O(1) constant space. We only allocate memory for three pointers (dummy, fast, and slow) regardless of the size of the linked list. No additional structures, recursion stacks, or arrays are utilized.

Why Avoid Recursion?

A common alternative approach to identifying the Nth node from the tail is recursion, where the function calls itself until the end is reached, and counts backward as the stack unwinds. While elegant, the recursive approach introduces an O(L) auxiliary space complexity due to the implicit call stack. In production environments or competitive programming with tight memory constraints, large linked lists can cause a Stack Overflow exception. Thus, the iterative two-pointer technique with O(1) space is objectively superior.

Algorithmic Constraints

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Optimal One-Pass Solution in C++

While a trivial approach involves counting the total nodes first and then iterating again to find the target, we can satisfy the Follow up constraint by completing the task in a single pass. Using the fast and slow pointer methodology ensures optimal performance and elegant code structure.

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    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) {
        ListNode dummy(0, head);
        ListNode* fast = &dummy;
        ListNode* slow = &dummy;

        // Move fast n+1 steps ahead to maintain a gap of n between fast and slow
        for (int i = 0; i <= n; i++) {
            fast = fast->next;
        }

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

        // Safely bypass and remove the nth node from the end
        slow->next = slow->next->next;

        return dummy.next;
    }
};

// Helper function to dynamically create a linked list from an array
ListNode* createLinkedList(int arr[], int size) {
    if (size == 0) return nullptr;
    ListNode* head = new ListNode(arr[0]);
    ListNode* current = head;
    for (int i = 1; i < size; i++) {
        current->next = new ListNode(arr[i]);
        current = current->next;
    }
    return head;
}

// Helper function to sequentially print a linked list
void printLinkedList(ListNode* head) {
    while (head) {
        cout << head->val << " -> ";
        head = head->next;
    }
    cout << "NULL" << endl;
}

// Main execution block for testing the linked list removal algorithm
int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int size = sizeof(arr) / sizeof(arr[0]);
    int n = 2;  // Target: Remove the 2nd node from the end

    // Initialize linked list
    ListNode* head = createLinkedList(arr, size);

    cout << "Original List: ";
    printLinkedList(head);

    // Execute the removal logic
    Solution solution;
    head = solution.removeNthFromEnd(head, n);

    cout << "Updated List: ";
    printLinkedList(head);

    return 0;
}

Frequently Asked Questions

How do you remove the Nth node from the end of a linked list in one pass?

By using two pointers (fast and slow) initialized at a dummy node. Advance the fast pointer n+1 steps ahead, then move both pointers simultaneously. When the fast pointer reaches the end, the slow pointer will be right before the node to remove.

What is the time complexity of the two-pointer approach for removing a node?

The time complexity is O(L), where L is the total number of nodes in the linked list, because we traverse the list exactly once.

Why use a dummy node when removing the Nth node from a linked list?

A dummy node simplifies edge cases, such as when the node to be removed is the actual head of the linked list. It ensures the head can be cleanly removed without needing extra conditional logic to check if we are modifying the root.