How to Remove the Nth Node from the End of a Linked List?

Removing the nth node from the end of a linked list is a common question in coding interviews, and it tests your understanding of linked list manipulation. Let's explore how to tackle this problem step by step.

First, let's understand the structure of a singly linked list. Each node contains a value and a reference to the next node. Here’s a simple definition of a node in Python:

PythonCopy code

Given the head of the linked list and an integer n, the task is to remove the nth node from the end of the list. A naive approach might involve calculating the length of the list and then locating the node to be removed, but with this method, we traverse the list twice.

A more efficient approach involves using the two-pointer technique, which allows us to solve the problem in one pass. Here’s how it can be accomplished:

1. Use two pointers, first and second. Move first n steps ahead in the list.
2. Move both first and second pointers simultaneously until first reaches the end of the list. At this point, second will be just before the nth node from the end.
3. Modify the next pointer of second to skip the target node.

Here’s the Python code to demonstrate this approach:

PythonCopy code

In this code, a dummy node is created to simplify edge cases, such as when the node to be removed is the head of the list. After initializing both pointers to the dummy node, the first pointer is moved n + 1 steps forward. This guarantees that when first reaches the end of the list, the second pointer will be located at the node just before the one we need to remove.

This method runs in O(L) time, where L is the length of the linked list, and it uses O(1) space since we’re only using a constant amount of additional space regardless of the input size.

Let's also consider a few corner cases:

• If the list has only one node and n is 1, the list will become empty.
• If n is equal to the length of the list, the first node should be removed.