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 node should be in the same order.

• All the values after node should be in the same order.

Examples

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.

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 node to be deleted is in the list and is not a tail node.

Intuition

Understanding the Problem

In this problem we will be given a node in a singly LinkedList, important thing to note here is that this node will not be the head(starting) of the LinkedList. This node is the one that we have to delete. Now since we're given a random node we don't know what comes before it(since it is a singly LinkedList). After deletion of node the following should happen in the LinkedList:

• The value of node should not exist.

• The number of nodes in LinkedList should decrease by one.

• All the values before node should remain the same.

• All the values after the node should remain the same.

The difficult part here is that we're given a random node due to which we don't know the previous of this node. If we knew the previous we could just point the next of previous to next of node and make node as nil. But that's not the case, hence we have to get creative.

Approach

The problem only says that the value of node should not exist in the LinkedList and rest of the values should remain the same. Which means we could just:

• Put node.next value in node.

• Point node.next to node.next.next.

This will make node value to be value of node.next.value. Now node.next will be node.next.next.

Code Solution

Python Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void Do not return anything, modify node in-place instead.
        """
        # make node value equal to node.next.value
        node.val=node.next.val
        # make node.next to point to node.next.next
        node.next=node.next.next

Time and Space Complexity

Time Complexity:

$$O(1)$$

As we're only updating the pointers.

Space Complexity:

$$O(1)$$

Since we're not allocating any extra space.

Conclusion

This problem as you can see only seems difficult but it is very easy. We just need to update the pointers of the given node.

Hope that explanation made sense and you found this blog helpful. If you've made it this far, please give it a like and drop a comment.

Happy Coding!🚀