grid47 Exploring patterns and algorithms
Oct 14, 2024
4 min read
Solution to LeetCode 237: Delete Node in a Linked List Problem
You are given a node in a singly linked list, and you are asked to delete this node from the list. The node is guaranteed to be not the last node in the list. After the deletion, the values before the node should remain in the same order, and the values after the node should also remain in the same order.
Problem
Approach
Steps
Complexity
Input: You are provided with the head of the linked list and a specific node to delete. The node will not be the last node in the list.
Example: Input: head = [1,2,3,4,5], node = 3
Constraints:
• The linked list will have at least two nodes.
• The value of each node is unique.
• The node to be deleted is guaranteed to not be the tail node.
Output: After deleting the given node, return the modified linked list with the node removed.
Example: Output: [1,2,4,5]
Constraints:
Goal: To delete the given node, we will copy the value of the next node into the current node and then delete the next node.
Steps:
• Copy the value of the next node into the current node.
• Point the current node's next to the node after the next node.
• Delete the next node.
Goal: The list will not be empty, and the given node will not be the last node in the list.
Steps:
Assumptions:
• The list is not empty.
• The node to be deleted is not the last node.
• Input: Input: head = [1,2,3,4,5], node = 3
• Explanation: The node to be deleted is 3. After deleting 3, the list becomes [1,2,4,5].
• Input: Input: head = [10,20,30,40], node = 20
• Explanation: The node to be deleted is 20. After deleting 20, the list becomes [10,30,40].
Approach: We can delete the given node by copying the value of the next node into the current node and adjusting the next pointer. This avoids the need for traversing the list from the start.
Observations:
• Since we are not given access to the head of the list, we cannot traverse the list from the start.
• The next node must exist, so we can safely copy its value into the current node.
• By copying the next node's value into the current node and removing the next node, the list remains in the correct order.
Steps:
• Step 1: Get the next node from the current node.
• Step 2: Copy the value of the next node into the current node.
• Step 3: Update the current node's next pointer to skip the next node and point to the node after it.
• Step 4: Delete the next node to free up memory.
Empty Inputs:
• The list will always have at least two nodes, so there are no empty list cases.
Large Inputs:
• The solution should work efficiently even for lists with up to 1000 nodes.
Special Values:
• The node to be deleted is guaranteed not to be the last node in the list.
Constraints:
• The problem guarantees that the node is not the last node, so no need to check for that.
Defines the `deleteNode` function which takes a pointer to a node (`node`) in a singly linked list as input and deletes it.
2 : Next Node Assignment
auto nxt = node->next;
Assigns the next node (`node->next`) to a temporary variable `nxt`.
3 : Copy Data from Next Node
*node =*nxt;
Copies the data and the next pointer of the next node (`nxt`) into the current node (`node`). This effectively overwrites the current node with the next node's data.
4 : Delete Next Node
delete nxt;
Deletes the next node (`nxt`). Since its data has already been copied to the current node, the node is effectively removed from the list.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(1)
Description: Since we are only modifying the node and its next pointer, the time complexity is constant.
Best Case: O(1)
Worst Case: O(1)
Description: We are only modifying the linked list in place, so the space complexity is constant.
