LeetCode 19 Solution: Remove the Nth Node from the End of a List

In this blog post, we’ll explore the LeetCode 19 Solution to the problem “Remove Nth Node from End of List.” This common interview question is a great way to practice linked list manipulation. I’ll show how to solve it efficiently in one pass, while keeping the code clear and easy to implement. Whether you’re preparing for coding interviews or looking to master linked list operations, this solution will enhance your problem-solving skills.

Problem Statement: Remove Nth Node from End of List

The task is simple: you are given the head of a linked list and a number n, and you need to remove the nth node from the end of the list. You return the new list’s head once you remove the node.

For example, consider the linked list [1, 2, 3, 4, 5]. If n = 2, we are required to remove the second node from the end, which is 4. The updated list should be [1, 2, 3, 5].

Understanding Linked Lists

Before diving into the solution, let’s make sure we understand what a linked list is. A linked list is a sequence of nodes where each node contains two elements:

1. The value stored in the node.
2. A pointer (or reference) to the next node in the list.

In a singly linked list, we can only traverse the list in one direction, from the head to the tail. The final node points to None, indicating the end of the list.

The Challenge: One-Pass Solution

The problem asks for a solution that removes the nth node from the end of the list in one pass. This means we cannot simply traverse the entire list twice, as that would take two passes. Instead, we need to come up with an approach that allows us to identify and remove the nth node in just a single traversal of the list.

Efficient Approach: The Two-Pointer Technique

To solve this problem efficiently, we can use a two-pointer technique. This technique involves using two pointers, often referred to as fast and slow, which traverse the linked list at different speeds or start at different positions. Here’s how it works:

1. Set up two pointers: Both pointers start at the beginning of the list. However, the fast pointer is moved n steps ahead of the slow pointer.
2. Move both pointers together: Once the fast pointer has moved n steps ahead, we move both pointers one step at a time until the fast pointer reaches the end of the list.
3. Remove the target node: When the fast pointer reaches the end, the slow pointer will be right before the node we need to remove. At this point, we adjust the pointers to skip the node.

This method ensures that we only need to traverse the list once, making it both efficient and easy to implement.

Implementing the LeetCode 19 Solution in Python

Here’s how the solution looks in Python:

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

def removeNthFromEnd(head: ListNode, n: int) -> ListNode:
    # Create a dummy node pointing to the head
    dummy = ListNode(0)
    dummy.next = head
    fast = slow = dummy

    # Move fast pointer n+1 steps ahead
    for _ in range(n + 1):
        fast = fast.next

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

    # Remove the nth node by skipping it
    slow.next = slow.next.next

    return dummy.next

The code starts by creating a dummy node, which simplifies handling edge cases, such as when the node to remove is the head itself. Both pointers (fast and slow) are initialized to this dummy node. The fast pointer is then moved n+1 steps ahead. This extra step lets the slow pointer stop just before the node to remove when the fast pointer reaches the end of the list. Finally, we adjust the next pointer of the slow node to skip the node that needs to be deleted, and return the updated list starting from the original head.

Handling Edge Cases

Understanding how to handle edge cases is important for writing robust code. Here are a few situations to consider:

• Single-node list: If the list contains only one node and you are asked to remove it (e.g., head = [1], n = 1), the result should be an empty list ([]).
• Removing the head node: If n equals the length of the list, the node to be removed is the head. The dummy node ensures that this case is handled correctly.
• Removing the last node: If n = 1, meaning the last node needs to be removed, the solution should still work since the slow pointer will point to the second-to-last node and will skip the last node.

Time and Space Complexity

The time complexity of this approach is O(sz), where sz is the number of nodes in the list. This is because we only make one traversal through the list. The space complexity is O(1) since we use a constant amount of extra space, independent of the size of the input.

Why This Solution Works Best

This two-pointer technique is an efficient and clean solution to the “remove nth node from end of list” problem. By using two pointers, we reduce the need for multiple traversals and ensure the algorithm runs in linear time. Additionally, the use of a dummy node helps manage edge cases and simplifies the logic for removing the head or other boundary nodes.

Final Thoughts

The LeetCode 19 Solution: Remove Nth Node from End of List is an excellent way to practice linked list operations and deepen your understanding of efficient algorithms. By mastering the two-pointer technique, you’ll be able to tackle a wide range of linked list problems with confidence.

If you’re preparing for coding interviews, make sure to practice problems like this one. Focus on understanding the core concepts of linked lists, pointers, and how to efficiently manipulate data structures to optimize performance. With consistent practice, you’ll gain the skills needed to solve even the most challenging problems.

Happy Coding!

---

Looking for more LeetCode solutions? Stay tuned for upcoming guides on tackling other LeetCode challenges in Python. Whether you’re preparing for technical interviews or aiming to improve your coding skills, exploring a variety of problems will enhance your understanding and proficiency.

You can find this problem on LeedCode, click here.