Remove Nth Node from End of List in Python (Time Complexity: O(n))

Understanding the Problem

The core challenge of this problem is to efficiently remove the nth node from the end of a singly linked list. This problem is significant in various applications such as managing playlists, task scheduling, and more. A common pitfall is misunderstanding the position of the nth node from the end, especially in edge cases like when the list has only one node.

Approach

To solve this problem, we can use a two-pointer technique to achieve a one-pass solution. Here's a step-by-step approach:

Naive Solution

The naive solution involves two passes through the list:

1. First, traverse the list to count the total number of nodes.
2. Then, traverse the list again to find the (total - n + 1)th node from the beginning and remove it.

This approach is not optimal as it requires two passes through the list, resulting in a time complexity of O(2n).

Optimized Solution

The optimized solution uses a two-pointer technique to achieve the task in one pass:

1. Initialize two pointers, both starting at the head of the list.
2. Move the first pointer n steps ahead.
3. Then, move both pointers simultaneously until the first pointer reaches the end of the list.
4. At this point, the second pointer will be at the (total - n)th node, just before the node to be removed.
5. Adjust the pointers to remove the nth node from the end.

Algorithm

Here is a step-by-step breakdown of the optimized algorithm:

1. Create a dummy node that points to the head of the list. This helps handle edge cases where the head needs to be removed.
2. Initialize two pointers, both pointing to the dummy node.
3. Move the first pointer n+1 steps ahead to maintain a gap of n nodes between the two pointers.
4. Move both pointers simultaneously until the first pointer reaches the end of the list.
5. The second pointer will now be just before the node to be removed. Adjust its next pointer to skip the target node.
6. Return the next node of the dummy node as the new head of the list.

Code Implementation

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 that points to the head
    dummy = ListNode(0, head)
    first = dummy
    second = dummy
    
    # Move the first pointer n+1 steps ahead
    for _ in range(n + 1):
        first = first.next
    
    # Move both pointers until the first pointer reaches the end
    while first:
        first = first.next
        second = second.next
    
    # Remove the nth node from the end
    second.next = second.next.next
    
    # Return the new head of the list
    return dummy.next

Complexity Analysis

The time complexity of the optimized solution is O(n), where n is the number of nodes in the list. This is because we only traverse the list once. The space complexity is O(1) as we are using a constant amount of extra space.

Edge Cases

Consider the following edge cases:

• Single node list: Removing the only node should return an empty list.
• Removing the head node: The dummy node helps handle this case seamlessly.
• n equals the length of the list: The dummy node ensures the correct node is removed.

Testing

To test the solution comprehensively, consider the following test cases:

def print_list(head):
    result = []
    while head:
        result.append(head.val)
        head = head.next
    return result

# Test case 1
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
n = 2
print(print_list(removeNthFromEnd(head, n)))  # Output: [1, 2, 3, 5]

# Test case 2
head = ListNode(1)
n = 1
print(print_list(removeNthFromEnd(head, n)))  # Output: []

# Test case 3
head = ListNode(1, ListNode(2))
n = 1
print(print_list(removeNthFromEnd(head, n)))  # Output: [1]

Thinking and Problem-Solving Tips

When approaching such problems, consider the following tips:

• Understand the problem requirements and constraints thoroughly.
• Think about edge cases and how to handle them.
• Break down the problem into smaller steps and solve each step methodically.
• Practice similar problems to improve problem-solving skills and familiarity with common patterns.

Conclusion

In this blog post, we discussed how to remove the nth node from the end of a linked list efficiently using a two-pointer technique. We covered the problem definition, approach, algorithm, code implementation, complexity analysis, edge cases, and testing. Understanding and solving such problems is crucial for developing strong problem-solving skills in computer science.

Additional Resources

For further reading and practice, consider the following resources:

• LeetCode Problem
• GeeksforGeeks Article
• Coursera Data Structures Course