Delete Node in a Linked List

The task here is to delete a node from a singly linked list when you have access to only that node (and not the head of the list). Since you cannot access the previous node, you cannot simply change its next pointer. Here’s how you can delete the node without accessing the previous one:

1. Copy the Value: Copy the value from the next node to the current node.
2. Update the Link: Make the current node’s next pointer point to the next node’s next node.
3. Delete Next Node: This way, the value from the next node is effectively “moved” to the current node, and the next node is skipped over.

Here is the code that implements this logic:

1
2
3
4
5

class Solution:
    def deleteNode(self, node):
        if node.next:
            node.val = node.next.val
            node.next = node.next.next

Explanation:

• node.val = node.next.val copies the value from the next node to the current node.
• node.next = node.next.next makes the current node’s next pointer skip the next node, effectively deleting it.

This approach works in constant time O(1) and does not require any additional space. It takes advantage of the fact that we don’t need to actually remove the node from memory; we only need to ensure that its value does not exist in the linked list and that the linked list’s order is maintained.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

# Definition for singly-linked list.
# class ListNode
#     attr_accessor :val, :next
#     def initialize(val)
#         @val = val
#         @next = nil
#     end
# end

# @param {ListNode} node
# @return {Void} Do not return anything, modify node in-place instead.
def delete_node(node)
    node.val = node.next.val
    node.next = node.next.next
end