Remove Nth Node From End of List

Two-Pointer Technique

In technical interviews, one common question candidates often encounter is how to remove the Nth node from the end of a linked list. This problem not only tests your grasp on linked list traversal but also evaluates your ability to implement efficient in-place algorithms using pointer manipulation.

This challenge is widely used by interviewers at top tech companies because it involves a solid understanding of data structures, especially linked list node removal and pointer handling. Whether you're preparing for FAANG interviews or optimizing your own code, mastering this problem sharpens your problem-solving approach for handling linked list-based problems.

Problem Statement with Example

Given a singly linked list, your task is to remove the Nth node from the end of the list and return the updated list's head.

Example:

Input: 1 → 2 → 3 → 4 → 5, N = 2
Output: 1 → 2 → 3 → 5

In the above case, the 2nd node from the end is 4, and it gets removed. The final linked list does not contain the fourth node, while all other nodes retain their relative positions.

This type of reverse index deletion is a classic example of when a simple data structure needs strategic traversal to achieve optimal performance.

Brute Force Approach – Two Passes Over the List

The most straightforward solution to this problem involves two full passes over the linked list:

• First, traverse the list and count the total number of nodes, say length.
• Then, calculate the node position from the start using length - N.
• Traverse again and remove that particular node.

Why It Works

This method works because once we know the length of the list, converting the reverse index into a forward index becomes trivial. However, this solution is not optimal in terms of traversal efficiency.

Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1) – no extra memory used except a few variables

Optimal One-Pass Approach Using Two-Pointer Technique

To enhance performance, we can use the two-pointer technique to perform the node removal in a single pass.

How the Fast and Slow Pointer Work

1. Initialize two pointers, fast and slow, at the head.
2. Move the fast pointer N steps ahead.
3. Now move both fast and slow one step at a time until fast.next becomes null.
4. At this point, slow is just before the node that needs to be deleted.

Handling Special Cases

If N is equal to the list's length, it means the head node needs to be removed. In such cases, simply return head.next.

Benefits of This Method

• Only one traversal of the list is required.
• More efficient for large linked lists.
• Maintains in-place deletion with O(1) extra space.

Time and Space Complexity

• Time Complexity: O(n)
• Space Complexity: O(1)

Python Code – One-Pass Solution

Here is a clean and efficient Python implementation using the two-pointer approach:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    dummy = ListNode(0, head)
    fast = slow = dummy

    for _ in range(n):
        fast = fast.next

    while fast.next:
        fast = fast.next
        slow = slow.next

    slow.next = slow.next.next
    return dummy.next

This code avoids extra memory, performs a single traversal, and efficiently removes the target node using pointer manipulation.

Edge Cases and Mistakes to Avoid

Here are some edge cases to keep in mind:

• Removing the head node: Happens when N equals the length of the list.
• Invalid N values: Ensure N is not greater than the number of nodes.
• Single-node list: If the list has only one node and N = 1, return None.

Common mistakes include:

• Not using a dummy node, which leads to complications while removing the head.
• Forgetting to check if fast.next is null before moving the pointer.

Real-World Use Cases of Nth Node Removal

This problem may seem theoretical but has practical applications in several areas:

• Undo operations: Where the most recent Nth action needs to be removed.
• Streaming data: In systems where the latest N items need periodic purging.
• Packet transmission: Dropping the Nth-last packet in a buffer.

Conclusion

Removing the Nth node from the end of a list is a fundamental problem that builds intuition for linked list manipulation and teaches how to optimize solutions through smarter traversal techniques. While the brute force approach is easier to understand, the two-pointer method is more efficient and interview-preferred. Whether you're tackling linked list problems or designing production-grade systems, mastering this concept is essential.

Use the two-pointer technique whenever a one-pass solution is needed, and always test your solution against edge cases to ensure reliability.