Remove Nth Node From End of List | Leetcode 19

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

Here’s the [Problem Link] to begin with.

Example 1:

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

Example 2:

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

Example 3:

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

Constraints:

• The number of nodes in the list is sz.
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

Follow up: Could you do this in one pass?

Solution 1: Brute Force Approach (Two Pass)

Intuition

Think of this like counting people in a line from the back! If you want to remove the 3rd person from the end, you first need to count how many people are in the line total. Then you can figure out which person to remove by doing some math. If there are 10 people and you want the 3rd from the end, you need to go to the 7th person from the front and remove the person next to them.

Detailed Approach

1. Calculate List Length: Walk through the entire list to count total nodes
2. Handle Edge Case: If n equals the length, remove the head node
3. Find Position: Calculate where to stop (length – n nodes from the start)
4. Navigate to Position: Move to the node just before the one we want to remove
5. Remove Node: Skip the target node by updating the next pointer

Code

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        if head is None:
            return None  # Empty list, nothing to remove

        length = 0
        current_node = head

        # First pass: Calculate the length of the linked list
        while current_node is not None:
            length += 1
            current_node = current_node.next

        # Special case: If the node to remove is the head of the list
        if length == n:
            new_head = head.next  # New head is the second node
            head = None           # Clean up old head
            return new_head

        # Find the node just before the one we want to remove
        position_to_stop = length - n  # Position of node before target
        current_node = head
        count = 1

        # Second pass: Navigate to the position just before target
        while count < position_to_stop:
            current_node = current_node.next
            count += 1

        # Remove the nth node from the end by skipping it
        current_node.next = current_node.next.next
        return head

Code Explanation

This solution uses two passes through the linked list. In the first pass, we count the total number of nodes to find the length. Once we know the length, we can calculate exactly which node to remove by converting “nth from the end” to “position from the beginning.” In the second pass, we navigate to the node just before our target and remove the target node by updating the next pointer to skip it. We handle the special case where we need to remove the head node separately.

Dry Run

Let’s trace through: 1 -> 2 -> 3 -> 4 -> 5, remove 2nd from end (n=2)

First Pass (Calculate Length):

• Visit nodes 1, 2, 3, 4, 5
• length = 5

Check Special Case:

• length (5) ≠ n (2), so not removing head

Find Position:

• position_to_stop = 5 – 2 = 3
• Need to go to position 3 (node 3)

Second Pass (Navigate):

• Start at node 1, count = 1
• Move to node 2, count = 2
• Move to node 3, count = 3
• Stop (count = position_to_stop)

Remove Node:

• current_node = node 3
• current_node.next = node 4
• Set current_node.next = node 4.next (which is node 5)
• Node 4 is removed!

Result: 1 -> 2 -> 3 -> 5

Time and Space Complexity

• Time Complexity: O(2n) – We traverse the list twice, but it’s still linear
• Space Complexity: O(1) – We only use a few variables

Simplifying It

This approach is like counting all the people in a line first, then figuring out which person to remove by doing some math. It’s straightforward but requires two trips through the line – one to count, one to remove.

Solution 2: Optimal Approach (Two Pointers – One Pass)

Intuition

Imagine you have two friends walking in a line, and you want one friend to be exactly n steps behind the other. If the front friend reaches the end of the line, the back friend will be exactly n steps from the end! This is the key insight – we don’t need to count the whole line first.

Detailed Approach

1. Set Up Two Pointers: Both start at the head of the list
2. Create Distance: Move the fast pointer n steps ahead
3. Handle Edge Case: If fast pointer reaches the end, we’re removing the head
4. Move Together: Move both pointers until fast pointer reaches the last node
5. Remove Node: The slow pointer will be just before the target node

Code

class Solution:
    def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
        fastp = head  # Fast pointer
        slowp = head  # Slow pointer

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

        # Special case: If fast pointer is None, remove head
        if fastp is None:
            return head.next

        # Move both pointers until fast reaches the last node
        while fastp.next is not None:
            fastp = fastp.next      # Move fast pointer forward
            slowp = slowp.next      # Move slow pointer forward

        # Remove the nth node from the end
        slowp.next = slowp.next.next
        return head

Code Explanation

We use two pointers with a fixed distance between them. First, we move the fast pointer n steps ahead to create the desired gap. If the fast pointer becomes None, it means we need to remove the head node. Otherwise, we move both pointers together until the fast pointer reaches the last node. At this point, the slow pointer is positioned just before the node we want to remove. We then remove the target node by updating the slow pointer’s next reference.

Dry Run

Let’s trace through: 1 -> 2 -> 3 -> 4 -> 5, remove 2nd from end (n=2)

Initial Setup:

• fastp = 1, slowp = 1

Create Distance (n=2 steps):

• Step 1: fastp = 2
• Step 2: fastp = 3
• Now fastp is 2 steps ahead of slowp

Check Special Case:

• fastp = 3 (not None), so not removing head

Move Both Pointers:

• Step 1: fastp = 4, slowp = 2
• Step 2: fastp = 5, slowp = 3
• Stop (fastp.next is None)

Remove Node:

• slowp = 3, slowp.next = 4
• Set slowp.next = 4.next (which is 5)
• Node 4 is removed!

Result: 1 -> 2 -> 3 -> 5

Time and Space Complexity

• Time Complexity: O(n) – We traverse the list only once
• Space Complexity: O(1) – We only use two pointer variables

Simplifying It

This approach is like having two friends walk together with a fixed distance between them. When the front friend reaches the end, the back friend is automatically at the right position. Much more efficient since we only need to walk through the line once!

Summary

The two pointers approach is generally preferred because it solves the problem in a single pass while using the same space complexity. However, the brute force approach is more intuitive and easier to understand when you’re first learning about linked list manipulation.

Both solutions effectively solve the problem, but the optimal solution showcases the power of the two-pointer technique, a fundamental skill for many linked list problems. The key insight is that we can maintain a fixed distance between two pointers to solve positional problems without needing to know the total length!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.