Delete Node in a Linked List (No Head)

🎯

Delete Node in a Linked List (No Head)

mediumLINKED_LISTAmazonFacebookMicrosoft

Imagine you have a chain of tasks linked together, but you only have access to the task you want to remove, not the start of the chain. How do you remove it without breaking the chain?

💡 This problem is tricky because you don't have access to the head of the linked list, which is usually needed to delete a node. Beginners often struggle to realize that you can delete a node by copying data from the next node instead of traditional pointer manipulation.

📋

Problem Statement

You are given a node in a singly linked list (except the tail), and you need to delete this node in-place without access to the head of the list. The input is the node to be deleted. Modify the linked list so that this node is removed.

The node to be deleted is not the tail node.The linked list contains at least two nodes.1 ≤ n ≤ 10^5 (number of nodes in the list)

💡

Example

Input"Linked list: 4 -> 5 -> 1 -> 9, node to delete = 5"

OutputLinked list after deletion: 4 -> 1 -> 9

We copy the value from the next node (1) into the node to delete (5), then bypass the next node.

• Deleting the first node (not head, but first accessible node) → list updates correctly
• Deleting a node in the middle → list remains connected
• Deleting the node just before the tail → tail remains intact
• Deleting a node when list size is minimal (2 nodes) → list reduces to single node

⚠️

Common Mistakes

Trying to delete the node by setting it to None/null

The linked list remains unchanged because the external reference is not updated

✅ Copy the next node's value and bypass the next node instead

Attempting to delete the tail node using this method

Leads to runtime error or undefined behavior since next node is null

✅ Check constraints and never attempt to delete tail node with this method

Not updating the next pointer after copying value

The list contains duplicate values and the node is not truly deleted

✅ Always update node.next to node.next.next after copying value

Forgetting to handle memory deallocation in languages like C++

Memory leak occurs as the deleted node is not freed

✅ Explicitly delete the bypassed node to free memory

Confusing node deletion with value deletion

Only the value changes but the node remains, causing logical errors

✅ Understand that deleting a node means removing it from the linked list structure

🧠

Brute Force (Traverse from Head to Delete Node)

💡 This approach exists to show the naive way of deleting a node by traversing from the head, which is impossible here but helps understand why the problem is unique.

Intuition

Normally, to delete a node, you find the previous node and change its next pointer. Without head access, this is impossible, so this approach highlights the limitation.

Algorithm

1. Start from the head of the list.
2. Traverse nodes until you find the node just before the node to delete.
3. Change the next pointer of the previous node to skip the node to delete.
4. Delete the node to delete (if manual memory management is needed).

💡 This algorithm is straightforward but impossible here because we don't have the head node, which is the key challenge.

</>

Code

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

def deleteNode(head, node):
    # This function is impossible without head, shown for understanding
    if head == node:
        head = head.next
        return head
    prev = head
    while prev and prev.next != node:
        prev = prev.next
    if prev and prev.next == node:
        prev.next = node.next
    return head

# Driver code to illustrate usage
if __name__ == '__main__':
    # Build list 4->5->1->9
    n4 = ListNode(9)
    n3 = ListNode(1, n4)
    n2 = ListNode(5, n3)
    n1 = ListNode(4, n2)
    head = n1
    # Delete node with value 5
    head = deleteNode(head, n2)
    # Print list
    curr = head
    while curr:
        print(curr.val, end=' -> ' if curr.next else '\n')
        curr = curr.next

Line Notes

def deleteNode(head, node):Defines function with head and node to delete, showing usual approach requires head

if head == node:Handles case if node to delete is head itself

while prev and prev.next != node:Traverse to find node before the node to delete

prev.next = node.nextBypass the node to delete by changing previous node's next pointer

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class Solution {
    public static ListNode deleteNode(ListNode head, ListNode node) {
        if (head == node) {
            head = head.next;
            return head;
        }
        ListNode prev = head;
        while (prev != null && prev.next != node) {
            prev = prev.next;
        }
        if (prev != null && prev.next == node) {
            prev.next = node.next;
        }
        return head;
    }

    public static void main(String[] args) {
        ListNode n4 = new ListNode(9);
        ListNode n3 = new ListNode(1);
        n3.next = n4;
        ListNode n2 = new ListNode(5);
        n2.next = n3;
        ListNode n1 = new ListNode(4);
        n1.next = n2;
        ListNode head = n1;

        head = deleteNode(head, n2);

        ListNode curr = head;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) System.out.print(" -> ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

public static ListNode deleteNode(ListNode head, ListNode node)Function signature showing head and node to delete

if (head == node)Check if node to delete is head

while (prev != null && prev.next != node)Traverse to find previous node

prev.next = node.nextSkip the node to delete by linking previous node to next node

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* deleteNode(ListNode* head, ListNode* node) {
    if (head == node) {
        ListNode* temp = head;
        head = head->next;
        delete temp;
        return head;
    }
    ListNode* prev = head;
    while (prev && prev->next != node) {
        prev = prev->next;
    }
    if (prev && prev->next == node) {
        prev->next = node->next;
        delete node;
    }
    return head;
}

int main() {
    ListNode* n4 = new ListNode(9);
    ListNode* n3 = new ListNode(1);
    n3->next = n4;
    ListNode* n2 = new ListNode(5);
    n2->next = n3;
    ListNode* n1 = new ListNode(4);
    n1->next = n2;
    ListNode* head = n1;

    head = deleteNode(head, n2);

    ListNode* curr = head;
    while (curr) {
        cout << curr->val;
        if (curr->next) cout << " -> ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

ListNode* deleteNode(ListNode* head, ListNode* node)Function signature with head and node to delete

if (head == node)Check if node to delete is head

while (prev && prev->next != node)Traverse to find previous node

prev->next = node->nextBypass node to delete by linking previous node to next node

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

function deleteNode(head, node) {
    if (head === node) {
        head = head.next;
        return head;
    }
    let prev = head;
    while (prev !== null && prev.next !== node) {
        prev = prev.next;
    }
    if (prev !== null && prev.next === node) {
        prev.next = node.next;
    }
    return head;
}

// Driver code
const n4 = new ListNode(9);
const n3 = new ListNode(1);
n3.next = n4;
const n2 = new ListNode(5);
n2.next = n3;
const n1 = new ListNode(4);
n1.next = n2;
let head = n1;

head = deleteNode(head, n2);

let curr = head;
while (curr !== null) {
    process.stdout.write(curr.val.toString());
    if (curr.next !== null) process.stdout.write(' -> ');
    curr = curr.next;
}
console.log();

Line Notes

function deleteNode(head, node)Function signature with head and node to delete

if (head === node)Check if node to delete is head

while (prev !== null && prev.next !== node)Traverse to find previous node

prev.next = node.nextBypass node to delete by linking previous node to next node

⏱

Complexity

TimeO(n)

SpaceO(1)

We traverse the list once to find the previous node, which takes O(n) time. No extra space is used.

💡 For n=100, this means up to 100 steps to find the node before the one to delete.

Interview Verdict: Impossible to implement in this problem as head is not given

This approach is shown to clarify why the problem is unique and why we need a different method.

🧠

Copy Next Node's Data and Delete Next Node (Optimal In-Place)

💡 This approach is the key insight: since we can't access the previous node, we copy the next node's value into the current node and delete the next node instead.

Intuition

Think of the node to delete as a placeholder. We overwrite it with the next node's data and then remove the next node, effectively deleting the original node's value.

Algorithm

1. Copy the value from the next node into the current node.
2. Change the current node's next pointer to skip the next node.
3. Delete the next node to free memory (if applicable).
4. The current node now effectively represents the next node, so the original node is deleted.

💡 This algorithm cleverly bypasses the need for the previous node by shifting the problem to the next node.

</>

Code

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

def deleteNode(node):
    node.val = node.next.val
    node.next = node.next.next

# Driver code
if __name__ == '__main__':
    n4 = ListNode(9)
    n3 = ListNode(1, n4)
    n2 = ListNode(5, n3)
    n1 = ListNode(4, n2)

    # Delete node with value 5
    deleteNode(n2)

    curr = n1
    while curr:
        print(curr.val, end=' -> ' if curr.next else '\n')
        curr = curr.next

Line Notes

def deleteNode(node):Function takes only the node to delete, no head needed

node.val = node.next.valCopy next node's value into current node to overwrite it

node.next = node.next.nextBypass the next node, effectively deleting it

while curr:Traverse and print list to verify deletion

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class Solution {
    public static void deleteNode(ListNode node) {
        node.val = node.next.val;
        node.next = node.next.next;
    }

    public static void main(String[] args) {
        ListNode n4 = new ListNode(9);
        ListNode n3 = new ListNode(1);
        n3.next = n4;
        ListNode n2 = new ListNode(5);
        n2.next = n3;
        ListNode n1 = new ListNode(4);
        n1.next = n2;

        deleteNode(n2);

        ListNode curr = n1;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) System.out.print(" -> ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

public static void deleteNode(ListNode node)Function takes only the node to delete

node.val = node.next.valOverwrite current node's value with next node's value

node.next = node.next.nextSkip the next node to delete it

while (curr != null)Print list to verify deletion

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

void deleteNode(ListNode* node) {
    node->val = node->next->val;
    ListNode* temp = node->next;
    node->next = node->next->next;
    delete temp;
}

int main() {
    ListNode* n4 = new ListNode(9);
    ListNode* n3 = new ListNode(1);
    n3->next = n4;
    ListNode* n2 = new ListNode(5);
    n2->next = n3;
    ListNode* n1 = new ListNode(4);
    n1->next = n2;

    deleteNode(n2);

    ListNode* curr = n1;
    while (curr) {
        cout << curr->val;
        if (curr->next) cout << " -> ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

void deleteNode(ListNode* node)Function takes only the node to delete

node->val = node->next->valCopy next node's value into current node

ListNode* temp = node->next;Store pointer to next node for deletion

node->next = node->next->next;Bypass next node to remove it from list

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

function deleteNode(node) {
    node.val = node.next.val;
    node.next = node.next.next;
}

// Driver code
const n4 = new ListNode(9);
const n3 = new ListNode(1);
n3.next = n4;
const n2 = new ListNode(5);
n2.next = n3;
const n1 = new ListNode(4);
n1.next = n2;

deleteNode(n2);

let curr = n1;
while (curr !== null) {
    process.stdout.write(curr.val.toString());
    if (curr.next !== null) process.stdout.write(' -> ');
    curr = curr.next;
}
console.log();

Line Notes

function deleteNode(node)Function takes only the node to delete

node.val = node.next.valOverwrite current node's value with next node's value

node.next = node.next.nextSkip the next node to delete it

while (curr !== null)Traverse and print list to verify deletion

⏱

Complexity

TimeO(1)

SpaceO(1)

Only constant time operations are performed: copying value and pointer adjustment.

💡 For any list size, this approach takes the same very short time.

Interview Verdict: Accepted and optimal

This is the standard solution expected in interviews for this problem.

🧠

Recursive Copy and Delete (Conceptual Alternative)

💡 This approach shows a recursive way to copy the next node's data and delete it, reinforcing the pointer trick concept.

Intuition

Recursively copy the next node's value into the current node until the node before tail is reached, then delete the tail.

Algorithm

1. If the next node is the tail, copy its value and set current node's next to null.
2. Otherwise, recursively call delete on the next node.
3. Copy the next node's value into the current node.
4. Effectively shift values backward and remove the last node.

💡 This approach is more complex and less efficient but helps understand the problem deeply.

</>

Code

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

def deleteNode(node):
    if node.next.next is None:
        node.val = node.next.val
        node.next = None
        return
    deleteNode(node.next)
    node.val = node.next.val

# Driver code
if __name__ == '__main__':
    n4 = ListNode(9)
    n3 = ListNode(1, n4)
    n2 = ListNode(5, n3)
    n1 = ListNode(4, n2)

    deleteNode(n2)

    curr = n1
    while curr:
        print(curr.val, end=' -> ' if curr.next else '\n')
        curr = curr.next

Line Notes

def deleteNode(node):Recursive function to delete node by shifting values

if node.next.next is None:Base case: next node is tail

node.val = node.next.valCopy next node's value into current node

deleteNode(node.next)Recursive call to delete next node

class ListNode {
    int val;
    ListNode next;
    ListNode(int val) { this.val = val; this.next = null; }
}

public class Solution {
    public static void deleteNode(ListNode node) {
        if (node.next.next == null) {
            node.val = node.next.val;
            node.next = null;
            return;
        }
        deleteNode(node.next);
        node.val = node.next.val;
    }

    public static void main(String[] args) {
        ListNode n4 = new ListNode(9);
        ListNode n3 = new ListNode(1);
        n3.next = n4;
        ListNode n2 = new ListNode(5);
        n2.next = n3;
        ListNode n1 = new ListNode(4);
        n1.next = n2;

        deleteNode(n2);

        ListNode curr = n1;
        while (curr != null) {
            System.out.print(curr.val);
            if (curr.next != null) System.out.print(" -> ");
            curr = curr.next;
        }
        System.out.println();
    }
}

Line Notes

public static void deleteNode(ListNode node)Recursive function to delete node by shifting values

if (node.next.next == null)Base case: next node is tail

node.val = node.next.valCopy next node's value into current node

deleteNode(node.next)Recursive call to delete next node

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

void deleteNode(ListNode* node) {
    if (node->next->next == nullptr) {
        node->val = node->next->val;
        delete node->next;
        node->next = nullptr;
        return;
    }
    deleteNode(node->next);
    node->val = node->next->val;
}

int main() {
    ListNode* n4 = new ListNode(9);
    ListNode* n3 = new ListNode(1);
    n3->next = n4;
    ListNode* n2 = new ListNode(5);
    n2->next = n3;
    ListNode* n1 = new ListNode(4);
    n1->next = n2;

    deleteNode(n2);

    ListNode* curr = n1;
    while (curr) {
        cout << curr->val;
        if (curr->next) cout << " -> ";
        curr = curr->next;
    }
    cout << endl;
    return 0;
}

Line Notes

void deleteNode(ListNode* node)Recursive function to delete node by shifting values

if (node->next->next == nullptr)Base case: next node is tail

node->val = node->next->valCopy next node's value into current node

deleteNode(node->next)Recursive call to delete next node

class ListNode {
    constructor(val) {
        this.val = val;
        this.next = null;
    }
}

function deleteNode(node) {
    if (node.next.next === null) {
        node.val = node.next.val;
        node.next = null;
        return;
    }
    deleteNode(node.next);
    node.val = node.next.val;
}

// Driver code
const n4 = new ListNode(9);
const n3 = new ListNode(1);
n3.next = n4;
const n2 = new ListNode(5);
n2.next = n3;
const n1 = new ListNode(4);
n1.next = n2;

deleteNode(n2);

let curr = n1;
while (curr !== null) {
    process.stdout.write(curr.val.toString());
    if (curr.next !== null) process.stdout.write(' -> ');
    curr = curr.next;
}
console.log();

Line Notes

function deleteNode(node)Recursive function to delete node by shifting values

if (node.next.next === null)Base case: next node is tail

node.val = node.next.valCopy next node's value into current node

deleteNode(node.next)Recursive call to delete next node

⏱

Complexity

TimeO(n)

SpaceO(n) due to recursion stack

Recursion depth can be up to n, copying values along the way.

💡 For n=100, this means up to 100 recursive calls, which is inefficient compared to O(1) solution.

Interview Verdict: Accepted but less efficient and not recommended

This approach is educational but not practical in interviews due to extra overhead.

📊

All Approaches - One-Glance Tradeoffs

💡 In 95% of interviews, code the optimal in-place copy-next-node approach because it is simple, efficient, and meets problem constraints.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force (Traverse from Head)	O(n)	O(1)	No	Yes	Mention only - impossible without head
2. Copy Next Node's Data and Delete Next Node	O(1)	O(1)	No	N/A	Code this - optimal and standard
3. Recursive Copy and Delete	O(n)	O(n) due to recursion	Yes	N/A	Mention as conceptual alternative, do not code

💼

Interview Strategy

💡 Use this guide to understand the problem deeply before interviews. Start by clarifying constraints, then explain the brute force impossibility, and finally present the optimal pointer trick solution.

How to Present

Step 1: Clarify that you only have access to the node to delete, not the head.Step 2: Explain the usual deletion method requires head and previous node, which is not available here.Step 3: Mention the brute force approach is impossible due to missing head.Step 4: Present the optimal approach of copying next node's data and deleting next node.Step 5: Write clean code and test with example inputs.

Time Allocation

Clarify: 2min → Approach: 3min → Code: 5min → Test: 3min. Total ~13min

What the Interviewer Tests

The interviewer tests your understanding of linked list pointer manipulation and your ability to think around constraints by using in-place tricks.

Common Follow-ups

• What if the node to delete is the tail? → Cannot delete without head, discuss alternatives.
• How to delete a node if you have access to head? → Use previous pointer traversal.
• Can this approach be used for doubly linked lists? → Yes, but simpler with previous pointer.
• What are the risks of this approach? → Cannot delete tail, and may cause issues if node is shared.

💡 These follow-ups test your understanding of problem constraints and edge cases.

🔍

Pattern Recognition

When to Use

1) You are asked to delete a node in a singly linked list. 2) You do not have access to the head of the list. 3) The node to delete is guaranteed not to be the tail. 4) You need an in-place solution with O(1) time.

Signature Phrases

'node to be deleted is not the tail node''you do not have access to the head of the list'

NOT This Pattern When

Deleting a node when head is given or doubly linked list deletion

Similar Problems

Remove Nth Node From End of List - also involves pointer manipulationIntersection of Two Linked Lists - uses pointer tricks to find intersectionRotate List - pointer manipulation without extra space

Practice

1. Consider the following buggy code snippet for adding two linked lists representing numbers in forward order. Which line contains the subtle bug that causes incorrect results when the sum produces a carry beyond the most significant digit?

medium

A. Line 2: Calculating length of l1

B. Line 7: Calling addListsHelper recursively

C. Line 4: Padding the shorter list

D. Line 9: Returning head without handling carry

Solution

1. Step 1: Identify carry handling after addition

   The code calls addListsHelper which returns carry, but the carry is ignored before returning the head.

2. Step 2: Understand impact of missing carry

   If carry is non-zero, the result should prepend a new node with carry value; missing this causes incorrect sum for cases like 999 + 1.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Carry ignored after addition leads to wrong output length [OK]

Hint: Always check carry after recursive addition [OK]

Common Mistakes:

• Ignoring carry after final addition
• Incorrect padding causing misalignment
• Modifying input lists unexpectedly

2. Identify the bug in the following code snippet intended to find the intersection node of two singly linked lists using the two-pointer approach:

medium

A. Line 6: Using '!=' instead of 'is not' to compare nodes

B. Line 8: Not checking if headA or headB is None before starting

C. Line 9: Incorrectly resetting pA and pB to headB and headA respectively

D. Line 10: Returning pA instead of pB

Solution

1. Step 1: Understand node comparison

   Nodes must be compared by reference, not by value. Using '!=' compares values, not references, causing incorrect intersection detection.

2. Step 2: Identify correct comparison operator

   'is not' compares object identity, ensuring correct detection of intersection node.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Using '!=' causes false positives or misses intersection [OK]

Hint: Use 'is' or 'is not' to compare nodes, not '==' or '!=' [OK]

Common Mistakes:

• Comparing node values instead of references
• Forgetting to handle empty lists
• Infinite loops due to pointer reset errors

3. What is the space complexity of the recursive approach to remove the nth node from the end of a singly linked list of length n?

medium

A. O(1) -- constant extra space since no data structures are used

B. O(n) -- due to recursion stack frames for each node

C. O(log n) -- recursion depth is logarithmic due to divide and conquer

D. O(n) -- due to auxiliary arrays used to store node references

Solution

1. Step 1: Identify recursion depth

   Recursion visits each node once, so recursion stack depth is n.

2. Step 2: Analyze space usage

   No extra arrays or data structures are used, but recursion stack frames consume O(n) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Recursion stack space grows linearly with list length [OK]

Hint: Recursion stack space equals max call depth [OK]

Common Mistakes:

• Assuming constant space for recursion
• Confusing recursion with iterative approach
• Thinking recursion depth is logarithmic

4. Suppose the digits in the input linked lists are stored in forward order (most significant digit first). Which modification to the in-place iterative addition algorithm is necessary to correctly add the two numbers?

hard

A. Traverse both lists once, adding digits directly without reversing, handling carry forward.

B. Create new nodes for the sum since in-place modification is impossible with forward order.

C. Use recursion to add digits from head to tail, passing carry backward.

D. Reverse both input lists, apply the in-place addition, then reverse the result list back.

Solution

1. Step 1: Understand forward order challenge

   Digits stored most significant first require addition from tail to head to handle carry properly.

2. Step 2: Reverse input lists

   Reversing both lists converts them to reverse order, allowing reuse of the in-place addition algorithm.

3. Step 3: Reverse result list

   After addition, reverse the result to restore forward order.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Reversing lists enables correct carry handling in forward order [OK]

Hint: Reverse lists to reuse reverse-order addition logic [OK]

Common Mistakes:

• Trying to add forward order lists without reversing
• Assuming carry can be handled left-to-right easily
• Creating new lists unnecessarily

5. Suppose you want to merge k sorted linked lists but now the lists can contain duplicate values and you want to return only the top M smallest unique values in sorted order. Which modification to the min-heap approach correctly achieves this?

hard

A. Use a min-heap and maintain a hash set to skip duplicates when extracting nodes, stopping after M unique values.

B. Use the same min-heap approach but stop after extracting M nodes, ignoring duplicates.

C. Merge all lists into one array, remove duplicates, sort, and return first M values.

D. Sequentially merge lists and remove duplicates during merge until M unique values are collected.

Solution

1. Step 1: Understand requirement for unique values

   Duplicates must be skipped, and only M unique smallest values returned.

2. Step 2: Modify min-heap approach

   Maintain a hash set to track seen values; when popping from heap, skip if duplicate; stop after M unique values.

3. Step 3: Why other options fail

   Stopping after M nodes ignores duplicates; merging all nodes wastes time and space; sequential merges are inefficient.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Hash set + min-heap ensures unique sorted extraction efficiently [OK]

Hint: Use hash set with min-heap to filter duplicates on the fly [OK]

Common Mistakes:

• Stopping after M nodes without filtering duplicates
• Sorting all nodes wastes time
• Sequential merges inefficient for large k