Solving Remove Nth Node From End in Python: Step-by-Step Guide

Introduction to the Remove Nth Node From End Problem

The "Remove Nth Node From End of List" is a classic linked list problem frequently encountered in coding interviews and algorithm challenges. The task is straightforward: given the head of a singly linked list and an integer n, remove the n-th node from the end of the list and return the updated head. While the problem statement sounds simple, it tests your understanding of linked list traversal, pointer manipulation, and edge case handling.

This problem matters because it appears regularly on platforms like LeetCode (Problem 19) and is a staple in technical interviews at major tech companies. It evaluates whether a developer can think about two-pass versus one-pass solutions, handle boundary conditions such as removing the head node, and write clean, bug-free pointer code.

Understanding the Problem

Before diving into code, let's clarify the problem with an example. Consider a linked list: 1 -> 2 -> 3 -> 4 -> 5 and n = 2. The 2nd node from the end is node 4. After removal, the list becomes 1 -> 2 -> 3 -> 5.

Key observations to keep in mind:

• The list is singly linked, meaning you can only traverse forward.
• n is always valid, meaning 1 <= n <= length of list.
• Removing the first node (when n equals the list length) is a valid edge case.
• You must return the head of the modified list.

Defining the ListNode Class

In Python, we first need a class to represent each node in the linked list. This class holds a value and a reference to the next node.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_linked_list(values):
    """Helper to build a linked list from a Python list."""
    dummy = ListNode(0)
    current = dummy
    for v in values:
        current.next = ListNode(v)
        current = current.next
    return dummy.next

def print_linked_list(head):
    """Helper to print linked list values."""
    result = []
    while head:
        result.append(str(head.val))
        head = head.next
    print(" -> ".join(result))

These helper functions make it easier to construct and visualize linked lists during testing.

Approach 1: Two-Pass Solution

The most intuitive approach is to traverse the list twice. In the first pass, count the total number of nodes. In the second pass, move to the node just before the one to be removed (which is at position length - n), and adjust its next pointer to skip the target node.

Implementing the Two-Pass Solution

def remove_nth_from_end_two_pass(head, n):
    # Step 1: Count the total length
    length = 0
    current = head
    while current:
        length += 1
        current = current.next

    # Step 2: Find the node before the one to remove
    # Use a dummy node to handle edge case of removing the head
    dummy = ListNode(0, head)
    current = dummy
    for _ in range(length - n):
        current = current.next

    # Step 3: Skip the target node
    current.next = current.next.next

    return dummy.next

The dummy node is a crucial trick here. Without it, removing the head node would require special-case logic. By placing a dummy node before the head, every removal becomes a uniform operation on current.next.

Time and Space Complexity

The two-pass solution runs in O(L) time, where L is the length of the list, because we traverse the list twice. The space complexity is O(1) since we only use a few pointers regardless of input size.

Approach 2: One-Pass Solution Using Two Pointers

The optimal solution uses the two-pointer technique to solve the problem in a single pass. The idea is to maintain two pointers, fast and slow, separated by exactly n nodes. When fast reaches the end of the list, slow will be positioned just before the node to remove.

How the Two-Pointer Technique Works

1. Initialize both fast and slow pointers at the dummy node.
2. Advance fast by n + 1 steps so that the gap between fast and slow is n nodes.
3. Move both fast and slow forward one step at a time until fast reaches the end.
4. At this point, slow.next is the node to remove. Skip it by setting slow.next = slow.next.next.

Implementing the One-Pass Solution

def remove_nth_from_end(head, n):
    dummy = ListNode(0, head)
    fast = dummy
    slow = dummy

    # Move fast n+1 steps ahead so the gap is n nodes
    for _ in range(n + 1):
        fast = fast.next

    # Move both until fast reaches the end
    while fast:
        fast = fast.next
        slow = slow.next

    # Remove the target node
    slow.next = slow.next.next

    return dummy.next

This solution is elegant because it eliminates the need to know the list length in advance. The gap between the two pointers naturally encodes the distance from the end.

Time and Space Complexity

The one-pass solution also runs in O(L) time but only requires a single traversal. Space complexity remains O(1). While the asymptotic complexity is the same as the two-pass approach, the one-pass solution is generally preferred in interviews because it demonstrates mastery of pointer manipulation.

Testing the Solution

Thorough testing is essential to verify correctness. Let's write test cases covering normal scenarios and edge cases.

# Test 1: Remove node from the middle
head = build_linked_list([1, 2, 3, 4, 5])
result = remove_nth_from_end(head, 2)
print_linked_list(result)  # Output: 1 -> 2 -> 3 -> 5

# Test 2: Remove the head node
head = build_linked_list([1, 2, 3, 4, 5])
result = remove_nth_from_end(head, 5)
print_linked_list(result)  # Output: 2 -> 3 -> 4 -> 5

# Test 3: Remove the tail node
head = build_linked_list([1, 2, 3, 4, 5])
result = remove_nth_from_end(head, 1)
print_linked_list(result)  # Output: 1 -> 2 -> 3 -> 4

# Test 4: Single node list
head = build_linked_list([1])
result = remove_nth_from_end(head, 1)
print_linked_list(result)  # Output: (empty)

# Test 5: Two node list, remove first
head = build_linked_list([1, 2])
result = remove_nth_from_end(head, 2)
print_linked_list(result)  # Output: 2

Each test case targets a specific scenario. The single-node and head-removal cases are particularly important because they are the most common sources of bugs in linked list manipulation.

Best Practices

• Always use a dummy node: The dummy node simplifies edge cases, especially when the head might be removed. It eliminates the need for special conditional logic.
• Draw the pointers on paper: Linked list problems are notoriously error-prone. Sketching the pointer movements before coding prevents off-by-one errors.
• Test edge cases explicitly: Single-node lists, two-node lists, removing the head, and removing the tail should all be covered in your test suite.
• Avoid memory leaks in languages that require manual management: While Python handles garbage collection automatically, in languages like C++ you should explicitly delete the removed node.
• Prefer the one-pass solution in interviews: It demonstrates deeper algorithmic thinking and pointer mastery, even though the time complexity is technically the same.
• Validate inputs when needed: In production code, check that head is not None and that n is within valid bounds, even if the problem guarantees these constraints.

Common Pitfalls

One frequent mistake is forgetting the dummy node, which leads to a NoneType error when trying to remove the head. Another common error is advancing the fast pointer by n instead of n + 1 steps, which causes the slow pointer to land on the wrong node. Always remember that you need slow to stop at the node before the target, not on the target itself.

Developers also sometimes attempt to solve this by converting the linked list to a Python list, removing the element, and rebuilding the list. While this works, it uses O(L) extra space and defeats the purpose of the exercise, which is to practice in-place pointer manipulation.

Conclusion

The Remove Nth Node From End problem is a foundational linked list challenge that every developer should master. By understanding both the two-pass and one-pass approaches, you gain valuable intuition about pointer manipulation, the dummy node technique, and the two-pointer pattern that appears across many algorithmic problems. The one-pass solution using fast and slow pointers is the most elegant and interview-preferred approach, achieving O(L) time and O(1) space with a single traversal. Practice this problem until the pointer movements become second nature, as the same techniques transfer directly to more advanced challenges like detecting cycles, finding the middle of a list, and merging sorted linked lists.