Delete without head pointer

Summary

Delete a node in a linked list given only the key value of the node to be deleted. This problem does not provide a reference to the node, only its value. We need to traverse the linked list and remove the node with the given key.

Detailed Explanation

To solve this problem, we will iterate through the linked list until we find the node with the given key. Once found, we will remove it by updating the next pointers of the adjacent nodes.

Here's a step-by-step breakdown of the solution:

Initialize a variable curr to point to the first node in the linked list.
Iterate through the linked list until we find the node with the given key:
- If the current node's value matches the key, remove it.
- Update curr to point to the next node.
If the node is found and removed, update curr to point to the node that was previously after the removed node (or the start of the list if the removed node was the first one).
Continue iterating until we have traversed the entire linked list.

Time complexity: O(n), where n is the number of nodes in the linked list. Space complexity: O(1), as we only use a constant amount of space to store temporary variables.

Optimized Solutions

Java

public void deleteNode(int key) { ListNode curr = head; while (curr != null && curr.val != key) { curr = curr.next; } if (curr == null || curr.next == null) { return; // node not found or only one node in the list } int val = curr.next.val; curr.next = curr.next.next; // Update the value of the current node to the value of the deleted node curr.val = val; }