Understanding deletion at a given distance
Deleting a node at a distance X is similar to inserting a node at a given distance. Just like inserting at a distance X We can solve this problem without keeping track of the previous node while traversing. However, we must consider a few special cases, so let’s examine them.
1. The list is empty
When the list is empty, meaning it contains no elements, any attempt to delete a node is unnecessary because there are no nodes in the list. Since there is nothing to remove, the list remains unchanged. We can return the existing head, as the list is empty, and no node needs to be deleted.
The list is empty
Algorithm
- Step 1: Return the original head node.
2. X = 0
When X equals 0, we need to delete the first node. We have previously covered this concept. We should update the head to store the reference to the second node and then delete the old head.
X = 0
Algorithm
- Step 1: Create a temporary pointer to store the current head node.
- Step 2: Move the head pointer to the next node.
- Step 3: Delete the original head node to free up memory.
- Step 4: Return the new head node.
3. X < size of the list
When we need to delete a specific node from a list, we should traverse the list until we reach the node just before the one we want to delete. Keep track of the current node and traverse X-1 steps instead of X. At the end of the loop, we will reach the node one step before the node that needs to be deleted. Then, the problem becomes deleting a node after a given node, where the given node is the node one step before the node that has to be deleted. Update the reference in the given node's next pointer to point to the node after the one that has to be deleted. Once the connections have been updated, safely delete the next node.
X < size of the list
Algorithm
- Step 1: Traverse the distance X - 1 while keeping track of the `current` node.
- Step 2: Set the `next` pointer of the `current` node to hold the node's reference stored in the `next` pointer of the node to be deleted.
- Step 3: Delete the node after the `current` node to free up memory.
- Step 4: Return the original head node.
4. X >= the size of the list
This indicates an invalid query. For example, we cannot delete the 10th node in a list of size 3. We will return the existing head node.
X could range from 0 to 4, meaning [0, 4]. Therefore, an input 5 would be invalid. It's important to note that X represents the distance from the head node, not the node's position.X >= size of the list
Algorithm
- Step 1: Traverse the distance X - 1 while keeping track of the `current` node.
- Step 2: Return the original head node.
Implementation
When implementing the logic for deleting nodes at a distance, we consider all the possible cases and write the code for each in conditional blocks.
C++
Java
Typescript
Javascript
Python
Complexity Analysis
The time complexity of deleting a node at a given distance X depends on the value of X and the size of the linked list. Since the list must be traversed up to the specified distance to locate the node, the number of operations varies based on how far the node is from the beginning.
Best case
The best case occurs when X is equal to 0. In this case, the function must delete the first node of the list. This process takes constant time, regardless of the linked list's size.
Best case: Delete the first node
Worst case
On the other hand, the worst case occurs when X is one less than the size of the list. In this case, the function must delete the last node of the list. This process takes linear time proportional to the length of the linked list, i.e., O(N).
Worst case: Delete the last node
The function's space complexity is constant, as it only creates a few variables that take up a fixed amount of space regardless of the size of the linked list.
Best Case - When X = 0
- Space Complexity - O(1)
- Time Complexity - O(1)
Worst Case - When X = length of the list - 1
- Space Complexity - O(1)
- Time Complexity - O(N)