Delete a node in linked list
Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.
Example:
Input: head = [1,2,3,4], node = 2
Output: [1,3,4]
Explanation: You are given the second node with value 2, the linked list should become 1 -> 3 -> 4 after calling your function.
Note:
- The linked list will have at least two elements.
- All of the nodes’ values will be unique.
- The given node will not be the tail and it will always be a valid node of the linked list.
- Do not return anything from your function.
Solution:
Since we can’t perform any operations on any node except for the node we want to delete. So we will solve this problem with an approach that will simple change the value of the node to be deleted to it’s next node’s value. After doing this, we will link that node to the next of the next node. Like this we can perform deletion.
Implementation:
Java:
class Solution {
public void deleteNode(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
}
Complexity Analysis:
- Time Complexity: O(1)
- Space Complexity: O(1).
