Delete Node in a Linked List | Can you solve it ?
Delete Node in a Linked List - Video Solution
Watch 10 video solutions for Delete Node in a Linked List, a medium level problem involving Linked List. This walkthrough by take U forward has 132,816 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- The value of the given node should not exist in the linked list.
- The number of nodes in the linked list should decrease by one.
- All the values before
nodeshould be in the same order. - All the values after
nodeshould be in the same order.
Custom testing:
- For the input, you should provide the entire linked list
headand the node to be givennode.nodeshould not be the last node of the list and should be an actual node in the list. - We will build the linked list and pass the node to your function.
- The output will be the entire list after calling your function.
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:
- The number of the nodes in the given list is in the range
[2, 1000]. -1000 <= Node.val <= 1000- The value of each node in the list is unique.
- The
nodeto be deleted is in the list and is not a tail node.
Approach Overview
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.
Complexity Analysis
| 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 |