There is a singly-linked list head and we want to delete a node node in it.
You are given the node to be deleted node. You will not be given access to the first node of head.
All the values of the linked list are unique, and it is guaranteed that the given node node is not the last node in the linked list.
Delete the given node. Note that by deleting the node, we do not mean removing it from memory. We mean:
node should be in the same order.node should be in the same order.Custom testing:
head and the node to be given node. node should not be the last node of the list and should be an actual node in the list.
Example 1:
Input: head = [4,5,1,9], node = 5 Output: [4,1,9] Explanation: You are given the second node with value 5, the linked list should become 4 -> 1 -> 9 after calling your function.
Example 2:
Input: head = [4,5,1,9], node = 1 Output: [4,5,9] Explanation: You are given the third node with value 1, the linked list should become 4 -> 5 -> 9 after calling your function.
Constraints:
[2, 1000].-1000 <= Node.val <= 1000node to be deleted is in the list and is not a tail node.Problem Overview: You’re given a reference to a node inside a singly linked list, not the head. The task is to delete that node from the list while keeping the rest of the list intact. The constraint is the key challenge: without access to the previous node, you can’t perform the usual pointer update.
Approach 1: Copy and Bypass (O(1) time, O(1) space)
This trick avoids needing the previous node. Copy the value from the next node into the current node using node.val = node.next.val. Then bypass the next node by updating the pointer: node.next = node.next.next. The original "next" node effectively disappears from the list. This works because the node to delete is guaranteed not to be the tail, so node.next always exists. The structure of the linked list remains valid and the deletion appears as if the original node was removed.
Approach 2: Utilize Two Pointers (O(n) time, O(1) space)
If the head of the list is available, you can traverse the list to locate the previous node. Use two pointers: one iterating through the list and another tracking the previous node. When the current pointer matches the node that needs deletion, update prev.next = curr.next to unlink it. This is the standard deletion method in a singly linked list. The traversal introduces linear time complexity, similar to many two pointer scanning patterns where one pointer follows another through the structure.
Recommended for interviews: The expected solution is the Copy and Bypass approach. Interviewers want to see whether you recognize the constraint that the previous node is unavailable. Copying the next node’s value and skipping it demonstrates a deep understanding of pointer manipulation in linked lists. The traversal approach shows baseline knowledge, but the O(1) trick is the real signal of problem-solving skill.
This approach leverages the fact that we have access to the node to be deleted and that deletion does not mean removing from memory but rather bypassing this node.
By copying the value from the next node to the node to be deleted and rearranging the pointers, we can effectively 'delete' the node without needing access to the head of the list.
In C, we access the next node, copy its value into the current node, and link to its next pointer. Finally, we free the memory of the next node to clean up.
Time Complexity: O(1) since we're performing constant-time operations.
Space Complexity: O(1) because we aren't using any auxiliary data structures.
This approach uses two pointers to manage nodes, allowing for a genuine swap and linkage manipulation. It reinforces the conceptual understanding of linked list pointer adjustments.
Note: The fundamentals are the same as we still replace and link to carry out the 'deletion'.
In C, we manage two pointers internally to achieve the same result, illustrating the necessity to understand pointer accessibility and connectivity.
Time Complexity: O(1), never fluctuating beyond direct node handling.
Space Complexity: O(1), not utilizing external structures.
We can replace the value of the current node with the value of the next node, and then delete the next node. This can achieve the purpose of deleting the current node.
Time complexity O(1), space complexity O(1).
Python
Java
C++
Go
TypeScript
JavaScript
C#
C
| Approach | Complexity |
|---|---|
| Copy and Bypass | Time Complexity: O(1) since we're performing constant-time operations. Space Complexity: O(1) because we aren't using any auxiliary data structures. |
| Utilize Two Pointers | Time Complexity: O(1), never fluctuating beyond direct node handling. Space Complexity: O(1), not utilizing external structures. |
| Node assignment | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Copy and Bypass | O(1) | O(1) | When only the target node is given and it is guaranteed not to be the tail |
| Two Pointers Traversal | O(n) | O(1) | When the head pointer is available and you want the standard deletion logic |
Delete Node in a Linked List | Can you solve it ? • take U forward • 129,658 views views
Watch 9 more video solutions →Practice Delete Node in a Linked List with our built-in code editor and test cases.
Practice on FleetCode