algoadvance

Leetcode 237. Delete Node in a Linked List

Problem Statement

You are given the head of a linked list and a node that needs to be deleted. You are provided access only to that node. The linked list node structure is defined as follows:

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

Write a function to delete the given node from the linked list.

Note that you should not return the head of the linked list; instead, you should mutate the given node’s value and pointers directly.

Clarifying Questions

  1. Q: Are we guaranteed that the provided node is not the tail of the list?
    • A: Yes, it is guaranteed that the node to be deleted is not the tail node.
  2. Q: What if the linked list contains only one node?
    • A: The problem guarantees that the node to be deleted is not the tail, so we assume the list has at least two nodes.
  3. Q: Should we handle any memory deallocation?
    • A: Since we are only provided one node and modify it in place, no explicit memory deallocation is necessary.

Strategy

Given only access to the node to be deleted:

  1. Copy the value from the next node to the current node.
  2. Update the current node’s next pointer to skip the next node.

This way, the current node effectively takes the place of the next node, thereby “deleting” itself.

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        // Ensure the node and its next are not null (although guaranteed by constraint)
        if (node == nullptr || node->next == nullptr) {
            return;
        }
        
        // Copy the data from the next node to the current node
        node->val = node->next->val;
        // Remove the next node by adjusting the pointers
        ListNode* nodeToDelete = node->next;
        node->next = node->next->next;
        // Optional but good practice: Explicit deallocation (uncomment if using a custom allocator)
        // delete nodeToDelete;
    }
};

Time Complexity

The time complexity of the above solution is (O(1)) because we are just copying values and updating pointers in constant time.

The space complexity is also (O(1)) since we are not using any additional space that scales with the input.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI