algoadvance

Leetcode 19. Remove Nth Node From End of List

Problem Statement

The task is to remove the N-th node from the end of a given linked list and return the head of the modified list.

For example:

Clarifying Questions

  1. What should we return when the list becomes empty?
    • Return nullptr if the resulting list is empty.
  2. Can n be greater than the length of the list?
    • No, it is guaranteed that n will be valid and within the bounds of the list.
  3. What is the expected time complexity?
    • Aim for O(n) time complexity where n is the number of nodes in the linked list.

Strategy

To achieve this, we can employ a two-pointer technique:

  1. Initialize two pointers, fast and slow, both pointing to the dummy node’s next node (essentially the head of the list).
  2. Move the fast pointer n steps forward.
  3. Move both fast and slow pointers one step at a time until fast reaches the end of the list. At this point, slow will be pointing to the node before the one we want to remove.
  4. Adjust pointers to skip the desired node.

This ensures that we can remove the nth node in one pass, achieving O(n) time complexity.

Code

#include <iostream>

// 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 simplify deletion process, especially the head node
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        
        // Initialize two pointers
        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;
        }
        
        // Skip the nth node from the end
        ListNode* nodeToDelete = slow->next;
        slow->next = slow->next->next;
        
        // Clean up memory
        delete nodeToDelete;
        
        // Get the new head node
        ListNode* newHead = dummy->next;
        delete dummy;
        
        return newHead;
    }
};

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

// Main function to test the solution
int main() {
    // Example list: 1->2->3->4->5
    ListNode* head = new ListNode(1);
    head->next = new ListNode(2);
    head->next->next = new ListNode(3);
    head->next->next->next = new ListNode(4);
    head->next->next->next->next = new ListNode(5);
    
    Solution solution;
    head = solution.removeNthFromEnd(head, 2);
    
    // Print the modified list
    printList(head);
    
    return 0;
}

Time Complexity

The time complexity of this algorithm is O(n) where n is the number of nodes in the linked list. This is because we essentially traverse the list twice (once for positioning the fast pointer and once to find the node to delete). This ensures an efficient single-pass operation after setup. The space complexity is O(1), as we only use a constant amount of extra space.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI