Dare2Solve
Given a node in a singly-linked list, delete the node from the list. The node to be deleted is not necessarily the last node. The list is represented as a series of nodes where each node contains a value and a pointer to the next node. The function should modify the linked list directly to remove the specified node.
Since we are not given access to the head of the list, the only way to delete a node is to copy the value from the next node into the current node and then remove the next node. This effectively "shifts" the data of the next node into the current node and removes the next node from the list. This approach works because we are guaranteed that the node to be deleted is not the last node.
Copy Value:
Move to Next Node:
Remove the Last Node:
next
pointer to null
. This effectively removes the last node from the list.Edge Cases:
Consider the linked list: 4 -> 5 -> 1 -> 9
and we need to delete node 5
.
1
into node 5
, the list becomes: 4 -> 1 -> 1 -> 9
.next
pointer of node 1
(formerly 5
) to null
, resulting in: 4 -> 1 -> 9
.O(1). The deletion operation involves a fixed number of steps: copying a value and updating pointers. It does not depend on the length of the list.
O(1). The algorithm uses a constant amount of extra space regardless of the size of the linked list.
class Solution {
public:
void deleteNode(ListNode* node) {
while (node->next && node->next->next) {
node->val = node->next->val;
node = node->next;
}
node->val = node->next->val;
node->next = nullptr;
}
};
class Solution:
def deleteNode(self, node: ListNode) -> None:
while node.next and node.next.next:
node.val = node.next.val
node = node.next
node.val = node.next.val
node.next = None
class Solution {
public void deleteNode(ListNode node) {
while (node.next != null && node.next.next != null) {
node.val = node.next.val;
node = node.next;
}
node.val = node.next.val;
node.next = null;
}
}
/**
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
var deleteNode = function(node) {
// console.log(node.next)
while (node.next && node.next.next) {
node.val = node.next.val;
node = node.next;
}
node.val = node.next.val;
node.next = null;
return;
};