Problem Title

Oracle Interview Question – Remove Nth Node From End of List

Problem Description

You are given the head of a singly linked list and an integer n.
Your task is to remove the n-th node from the end of the list and return the modified list.

Input Examples

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 between 1 and 30.

• Each node’s value is between 0 and 100.

• n is between 1 and the size of the list.

Objective

Solve the problem in one pass through the linked list.

Approach – Two Pointer Technique (Single Pass)

1. Create a dummy node that points to the head. This handles edge cases like deleting the first node.

2. Use two pointers, fast and slow, both starting from the dummy node.

3. Move the fast pointer n + 1 steps forward.

4. Move both fast and slow one step at a time until fast reaches the end.

5. Now, slow is just before the node that needs to be deleted.

6. Change slow->next to skip the target node.

7. Delete the target node to free memory.

8. Return dummy->next as the new head of the list.

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) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* fast = dummy;
        ListNode* slow = dummy;
        for (int i = 0; i <= n; i++) {
            fast = fast->next;
        }
        while (fast != nullptr) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* toDelete = slow->next;
        slow->next = slow->next->next;
        delete toDelete;
        return dummy->next;
    }
};

Key Concepts

• Dummy nodes simplify edge case handling.

• Two-pointer technique allows solving the problem in a single pass.

• Proper memory management is important to avoid leaks.