Delete Node in a Linked List - Solution & Explanation

Problem Overview: You are given a node in the middle of a singly linked list and must delete it. The head of the list is not provided, so you cannot traverse from the start to locate the previous node.

Approach 1: Copy and Bypass (O(1) time, O(1) space)

This approach avoids searching for the previous node entirely. Copy the value from the next node into the current node, then bypass the next node by updating node.next = node.next.next. The original next node effectively disappears from the list, which simulates deleting the given node. The key insight is that you cannot remove the current node without access to its predecessor, so you overwrite its value and remove the node after it instead. This technique is common in linked list problems where only a reference to the target node is available.

Approach 2: Utilize Two Pointers (O(n) time, O(1) space)

If the list head is available, you can traverse the list to locate the node immediately before the target node. Use two pointers: one pointer tracks the current node while another trails behind to maintain the previous reference. Once the target node is found, update the previous node's next pointer to skip it. This is the traditional deletion method used in singly linked lists. It relies on sequential traversal and pointer updates, a common pattern when working with two pointers or iterative traversal in linked list structures.

Recommended for interviews: Interviewers expect the Copy and Bypass trick because the problem explicitly removes access to the head node. Recognizing that you can overwrite the node’s value demonstrates strong understanding of pointer manipulation and linked list behavior. Mentioning the standard traversal deletion shows foundational knowledge, but the O(1) overwrite method is the intended solution.