Deleting the Nth Node from the End of a List

Problem Statement

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

Examples

Example 1:

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

Explanation: The 2nd node from the end is the node with value 4, so we remove it.

Example 2:

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

Explanation: The only node is removed, resulting in an empty list.

Constraints

• The number of nodes in the list is sz

• 1 <= sz <= 30

• 0 <= Node.val <= 100

• 1 <= n <= sz

Approach: Two-Pointer Technique

The key insight is to use two pointers with a gap of n nodes between them. When the fast pointer reaches the end, the slow pointer will be at the node just before the one we need to remove.

Algorithm Steps

• Create a dummy node: This handles the edge case where we need to remove the first node

• Initialize two pointers: Both start at the dummy node

• Move the fast pointer: Advance it n+1 steps to create the proper gap

• Move both pointers together: Advance both slow and fast pointers one step at a time until fast reaches the end (becomes NULL)

• Remove the target node: Now slow points to the node just before the target - skip the nth node from the end

• Return the result: Return dummy.next

Visual Walkthrough

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

Initial state: Both pointers start at dummy
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
↑
slow/fast

Step 1: Move ONLY fast pointer n+1 = 3 steps ahead
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
↑                   ↑
slow               fast

Step 2: Move BOTH pointers one step at a time until fast becomes null
Iteration 1:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
         ↑              ↑
        slow           fast

Iteration 2:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
              ↑              ↑
             slow           fast

Iteration 3:
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
                   ↑                   ↑
                  slow               fast (now null, loop stops)

Step 3: Now slow points to node 3 (just before target node 4)
Remove slow.next (which is node 4):
dummy -> 1 -> 2 -> 3 -> 5 -> null
                   ↑
                  slow

Final result: [1,2,3,5]

Implementation

C Solution

#include <stdio.h>
#include <stdlib.h>

struct ListNode {
    int val;
    struct ListNode *next;
};

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    // Create dummy node to handle edge cases
    struct ListNode dummy;
    dummy.val = 0;
    dummy.next = head;

    // Initialize two pointers
    struct ListNode* slow = &dummy;
    struct ListNode* fast = &dummy;

    // Move fast pointer n+1 steps ahead
    for (int i = 0; i <= n; i++) {
        fast = fast->next;
    }

    // Move both pointers until fast reaches end
    while (fast != NULL) {
        slow = slow->next;
        fast = fast->next;
    }

    // Store the node to be removed for potential cleanup
    struct ListNode* nodeToRemove = slow->next;

    // Remove the nth node from end
    slow->next = slow->next->next;

    // Free the removed node (optional, depends on memory management requirements)
    // free(nodeToRemove);

    return dummy.next;
}

// Helper function to create a new node
struct ListNode* createNode(int val) {
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

// Helper function to print the list
void printList(struct ListNode* head) {
    printf("[");
    while (head != NULL) {
        printf("%d", head->val);
        if (head->next != NULL) {
            printf(",");
        }
        head = head->next;
    }
    printf("]\n");
}

Alternative Approach: Two-Pass Solution

If the two-pointer technique feels complex, here's a simpler but less efficient approach:

struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
    // First pass: count total nodes
    int length = 0;
    struct ListNode* current = head;
    while (current != NULL) {
        length++;
        current = current->next;
    }

    // Handle edge case: removing first node
    if (length == n) {
        struct ListNode* newHead = head->next;
        // free(head); // optional memory cleanup
        return newHead;
    }

    // Second pass: find the node before target
    current = head;
    for (int i = 0; i < length - n - 1; i++) {
        current = current->next;
    }

    // Store and remove the target node
    struct ListNode* nodeToRemove = current->next;
    current->next = current->next->next;
    // free(nodeToRemove); // optional memory cleanup

    return head;
}

Complexity Analysis

Two-Pointer Approach

• Time Complexity: O(L), where L is the length of the list

• Space Complexity: O(1), constant extra space

Two-Pass Approach

• Time Complexity: O(L), but requires two traversals

• Space Complexity: O(1), constant extra space

Key Insights

1. Dummy Node Pattern: Using a dummy node simplifies edge case handling, especially when removing the first node

2. Two-Pointer Technique: Maintaining a fixed gap between pointers is a powerful technique for linked list problems

3. Edge Cases: Always consider removing the first node, last node, or the only node in the list

Common Pitfalls

1. Off-by-one errors: Make sure the gap between pointers is exactly right

2. Null pointer access: Always check for null before accessing next

3. Forgetting the dummy node: This makes removing the first node much harder

Practice Variations

• Remove the nth node from the beginning

• Remove all nodes at even positions

• Remove nodes with duplicate values

References and Sources

This problem is widely known as:

• LeetCode Problem #19: "Remove Nth Node From End of List" - Available at: https://leetcode.com/problems/remove-nth-node-from-end-of-list/

• GeeksforGeeks: Delete Nth node from the end of the given linked list - Available at: https://www.geeksforgeeks.org/dsa/delete-nth-node-from-the-end-of-the-given-linked-list/

• InterviewBit: Remove Nth Node from List End - Available at: https://www.interviewbit.com/problems/remove-nth-node-from-list-end/

Companies That Have Asked This Question

Based on interview preparation platforms, this problem has been asked by several top tech companies:

• Uber: This question appears in Uber interviews, as documented on interview preparation platforms

• Meta (Facebook): Meta has asked variations of this linked list problem in their technical interviews

• General FAANG Companies: This question is commonly asked at FAANG companies and is considered a standard linked list interview question

Educational Platforms Covering This Problem

• LeetCode: The primary source for this problem with official examples and test cases

• GeeksforGeeks: Comprehensive educational coverage with multiple solution approaches

• InterviewBit: Interview-focused preparation material

• HelloInterview: Provides detailed explanations for interview preparation

• Interviewing.io: Features this as a common technical interview question

Note: These are the interpretations of the standard algorithmic approach to this well-known computer science problem. The problem statement and examples follow the format established by LeetCode and other educational platforms.