Remove Nth Node from End of List | Leetcode 19 Solution

Problem Description

Given a linked list, remove nth node from end of list and return its head. The list can have various sizes, and the node we need to remove can be anywhere from the beginning to the end of the list.

Approach

To solve this problem efficiently, we need to think about how to traverse the linked list while maintaining the necessary reference to remove the nth node from the end.

Let’s break down the approach into different solutions, from the naive approach to the optimized approach.

Naive Approach for Remove Nth Node from End of List

The simplest approach involves two full passes over the linked list:

1. First pass: Traverse the list to get the length of the list.
2. Second pass: Traverse the list again to remove the (length – n)th node from the beginning.

Code Implementation

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Step 1: Find the length of the list
        int length = 0;
        ListNode temp = head;
        while (temp != null) {
            length++;
            temp = temp.next;
        }

        // Step 2: Find the node to remove (length - n)
        int target = length - n;
        temp = head;

        // Special case: Remove the first node
        if (target == 0) {
            return head.next;
        }

        // Traverse to the (length - n)th node
        for (int i = 0; i < target - 1; i++) {
            temp = temp.next;
        }

        // Remove the nth node from the end
        temp.next = temp.next.next;

        return head;
    }
}

Time and Space Complexity:

• Time Complexity: O(2 * L), where L is the length of the linked list. This is because we are making two passes: one to calculate the length and another to remove the node.
• Space Complexity: O(1), since we’re only using a few extra variables to store pointers.

Optimized Approach: Two Pointer Technique for Remove Nth Node from End of List

We can optimize the solution by using a two-pointer technique. Instead of making two full passes, we can use two pointers that are spaced n nodes apart. By the time the first pointer reaches the end of the list, the second pointer will be at the (n+1)-th node from the end. This allows us to remove the nth node from the end in just one pass.

Code Implementation

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // Create a dummy node to simplify edge cases (like removing the head node)
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy;
        ListNode second = dummy;

        // Move the first pointer n+1 steps ahead
        for (int i = 0; i <= n; i++) {
            first = first.next;
        }

        // Move both pointers until the first pointer reaches the end
        while (first != null) {
            first = first.next;
            second = second.next;
        }

        // Remove the nth node from the end
        second.next = second.next.next;

        return dummy.next;
    }
}

Time and Space Complexity:

• Time Complexity: O(L), where L is the length of the linked list. We make a single pass through the list using the two pointers.
• Space Complexity: O(1), since we only use a constant amount of extra space (for the two pointers).

Edge Cases to Consider for Remove Nth Node from End of List

• Removing the head node: If the node to be removed is the first node, the two-pointer technique with a dummy node ensures that this is handled efficiently.
• Single node list: If the list has only one node and we need to remove it, both approaches should return null.
• Removing the last node: The two-pointer approach allows us to easily handle the removal of the last node by updating the second pointer’s next field.

Conclusion

The Remove Nth Node from End of List problem on Leetcode can be solved in several ways. The naive approach requires two passes over the list, while the optimized solution using the two-pointer technique reduces it to a single pass, offering better performance.

• The Naive Approach is simple but less efficient, with a time complexity of O(2 * L).
• The Optimized Approach (Two-pointer technique) is more efficient with a time complexity of O(L), and it handles edge cases with minimal extra space.

Both approaches are helpful, but the two-pointer method is the preferred solution for large lists due to its efficiency.