Delete Node in a Linked List given only the node

Problem:

You are given a node to delete from a linked list.

But you are not given the head node.

Delete it in O(1) time and O(1) space complexity.

Constraints:

• The node values are unique
• The node to be deleted is not the tail node
• There are at least two nodes in the linked list

For example,

Given the linked list :

1 -> 4 -> 7 -> 8

And the node 7 to be deleted

The output should be

1 -> 4-> 8

Try out the solution here:

https://leetcode.com/problems/delete-node-in-a-linked-list/

Solution:

If we are given the head of a linked list then you can use the below algorithm to delete the node.

Use two pointer approach.

Have two pointers one always pointing to the previous node.

Another pointing to the current node.

Keep moving the pointers until you find out the node to be deleted.

At this moment the previous pointer will be pointing to the previous node and the current pointer will be pointing to the current node.

Make the next pointer of the previous node to point to the next node of the current pointer.

This way you remove the node from the linked list chain.

But in our case , we don’t have access to the head.

How can we delete the node in this case?

And that too in O(1) time and O(1) space complexity.

By removing the next node and copying the value of the next node to the current node.

All you have to do is:

Get the next node and store it in a temporary node.

Copy the value of the next node to the current node

Make the current node’s next pointer point to the next pointer of the temporary node.

Here is the code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public void deleteNode(ListNode node) {
        
        ListNode temp = node.next;


        node.next = temp.next;


        node.val  = temp.val;
        

        
    }
}

The time complexity and space complexity of the above solution is just O(1)

That’s it!