Remove Nth Node From End of List (Leetcode #19)
The "Remove Nth Node From End of List" problem from Leetcode is a common question in coding interviews, particularly when dealing with linked lists. In this blog, we'll cover the problem statement, discuss a brute force approach, give hints, and present an efficient solution with its time and space complexity.
Understanding the Problem Statement
You are given a singly linked list and need to remove the Nth node from the end of the list. The problem's goal is to modify the list in-place and return its head after removing the node. For example, given the list 1 → 2 → 3 → 4 → 5 and N = 2, the resulting list should be 1 → 2 → 3 → 5.
Brute Force Approach
A common brute force approach to solve this problem would be:
First, traverse through the entire linked list to determine its length,
L
.Calculate the position of the Nth node from the start:
L - N + 1
.Traverse the linked list again to this calculated position.
Update pointers to remove the desired node.
This approach, however, requires two passes through the list, which makes it inefficient for larger linked lists.
Hint to Solve the Problem Efficiently
A more efficient solution can be implemented by utilizing the "two-pointer technique". By using two pointers—one called fast
and one called slow
—you can keep a gap of n
nodes between them and traverse the list in a single pass. This technique helps to directly reach the node that needs to be removed without the need to calculate its position.
Efficient Solution
Let's walk through an efficient approach that uses only one pass, based on the given code:
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode(0) # Create a dummy node to simplify edge cases
dummy.next = head
slow, fast = dummy, head
# Move fast pointer so that the gap between slow and fast is n nodes apart
for _ in range(n):
fast = fast.next
# Move fast to the end, maintaining the gap
while fast:
fast = fast.next
slow = slow.next
# Skip the desired node
slow.next = slow.next.next
# Return head of the modified list
return dummy.next
Explanation:
A dummy node is created to handle edge cases (e.g., when the node to be removed is the head).
Two pointers—
slow
andfast
—are initialized, with thefast
pointer starting at the head and theslow
pointer starting at the dummy node.The
fast
pointer moves ahead byn
nodes, creating a gap ofn
nodes betweenslow
andfast
.Both pointers move one node at a time until
fast
reaches the end of the list.The
slow
pointer is now just before the node that needs to be removed. The next pointer ofslow
is updated to skip the node to be removed.Finally, the modified list's head is returned.
Time and Space Complexity
Time Complexity: The time complexity for this solution is O(N), where
N
is the number of nodes in the linked list. This is because we only make one pass through the list.Space Complexity: The space complexity is O(1), as we are only using a few pointers and not allocating any extra space for data structures that grow with the input size.
The two-pointer approach is efficient and ideal for solving this problem in a single traversal, making it a significant improvement over the brute force approach.
Conclusion
The "Remove Nth Node From End of List" problem is a great example of how linked list problems can often be solved efficiently using pointer manipulation. By understanding the two-pointer technique, we can solve this problem in a single traversal, optimizing both time and space complexity. This approach not only demonstrates an efficient solution but also highlights the importance of using dummy nodes to simplify edge cases in linked list operations. Mastering these techniques will greatly enhance your ability to solve similar linked list problems in coding interviews.