The O(n) Club: Deleting a Linked List Node When All You Have Is the Node (Not the Head!)

The O(n) Club: Deleting a Linked List Node When All You Have Is the Node (Not the Head!)

⚡ TL;DR

Your mission: delete a node in a singly linked list, but you don’t get the head — just a reference to the actual node (and it’s not the tail, so that’s something). The trick? Turn your node into its next-door neighbor, then ghost the neighbor from memory. Java’s garbage collector will sweep up the existential mess later.

// Java code: Given only the node itself (not head!)
void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

🧠 How Devs Usually Mess This Up

If your first instinct is, “I’ll just walk backwards to fix the previous pointer” — welcome to the world of singly linked lists, pal. Going backward is as possible as un-toasting bread. Others try to “remove” the current node, missing that you can’t update the node before it (since you can’t find it). And no, you really don’t need to worry about freeing memory — unless you’re writing in C while simultaneously fighting a bear.

🔍 What’s Actually Going On

Picture this: you’re managing a secret team of spies in a line (that’s the list). You’re told to eliminate an agent, but you’re not allowed to contact HQ (the head). Instead, you simply swap the soon-to-be-fired agent’s identity badge (value) with the next agent, then erase the next agent from everyone’s memory (skip over them). In other words: overwrite the value, then rewire the reference to jump over the next node. O(1) time, O(1) drama, and nobody gets their shoes dirty.

🛠️ PseudoCode

• Grab a reference to the node you must erase.
  The system provides you with direct access.
• Copy the value from the next node down.

  node.val = node.next.val;

  The current node shapeshifts into its successor.

• Point current node’s next at its next-next neighbor.

  node.next = node.next.next;

  The original next node vanishes from the line-up (and the party).

• Relax. Java’s garbage collector finishes the cleanup.

💻 The Code

// Definition for singly-linked list.
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}
 // Deletes the node (not the tail), given only that node
public void deleteNode(ListNode node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Tails are off-limits: Try this on the last node and Java will yeet a NullPointerException straight at you.
• No memory management needed: In Java, once a node is unlinked, say hello to automatic garbage collection (your ops guy will thank you).
• That node isn’t “gone” — it’s just… someone else now: If your code depends on unique node identities elsewhere, well, congrats on a new batch of hidden bugs.
• O(1) everything: No matter if your list is three nodes or three million, this trick is always instant and memory-light. No loops, no tears.

🧠 Interviewer Brain-Tattoo

“Can’t remove it? Overwrite it. Welcome to the fast lane of linked list problems, where we don’t need to know the head to chop from the middle.”