[Problem Solving] Delete a linked list node when head is not given

Given a linked list as shown below, delete a node when we have access to only that node.

Input: [1,2,3,4,5] Node to delete = 4

Output: [1,2,3,5]

Here are some of the assumptions that we will make for this problem.

• The linked list will have at least two nodes
• The node to delete won’t be a tail node and will be valid

Usually, when the head of a linked list is available, it is straightforward to traverse the list while keeping tracking of current and previous nodes. Once we reach the desired node to be deleted, we set its previous node’s next pointer to be the current node’s next element and re-wire some connections as shown below.

In this case, we don’t have access to the previous node. We have to delete it but preserve the value of the node next to it. So what we can do is to copy the value of the next node into the current node’s value and delete the next node.

Time Complexity: O(1)

Space Complexity: O(1)

Code for the above solution:

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution:
    def deleteNode(self, node):
        """
        :type node: ListNode
        :rtype: void
        """
        next_node = node.next
        node.val = next_node.val
        node.next = next_node.next
        next_node.next = None

Hope you enjoyed a simple solution to delete a linked list node when we have access only to that node. Have a great day!