Delete a node from linked list without head pointer
The problem at hand involves deleting a node from a singly linked list without having direct access to the head of the linked list. Linked lists are data structures that consist of nodes, where each node has a value and a reference to the next node in the sequence. Deleting a node typically requires updating the pointers of the previous node to bypass the node to be deleted and connect directly to the subsequent node. However, without a direct reference to the head node, this task becomes more challenging.

Problem Description
Given a singly linked list and a node in that linked list, your goal is to delete the specified node without having direct access to the head of the linked list. The challenge here is that you cannot simply traverse the list from the beginning to find the previous node, as you don't have a direct reference to the head.
Example
Let's take an example to better understand the problem:
Linked list: 1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
You want to delete the node with value 3 from the list.
Idea to Solve
Since you don't have the head pointer, you cannot directly traverse the list from the beginning. However, you can copy the value of the next node into the node you want to delete, effectively making it seem like you have deleted the node. You can then bypass the next node by updating the pointers of the current node.
Pseudocode
function deleteNode(ref, node):
if node is NULL:
return
if node.next is NULL:
// Cannot delete the last node
return
else:
// Copy value of next node into current node
node.data = node.next.data
// Get the node to be deleted
temp = node.next
// Bypass the next node
node.next = temp.next
// Free the memory of the deleted node
free(temp)
main:
create linked list sll
populate sll with values
display sll before deletion
call deleteNode(sll, node_to_delete)
display sll after deletion
Algorithm Explanation
- The
deleteNode
function takes a reference to the linked list (ref
) and the node to be deleted (node
) as input. - If the node is
NULL
, there's nothing to delete, so the function returns. - If the next node of the current node is
NULL
, it means the node to be deleted is the last node. In this case, you cannot delete it, so the function returns. - Otherwise, copy the value of the next node into the current node, effectively overwriting the value you want to delete.
- Get the reference to the node you want to delete (which is the next node).
- Update the pointers of the current node to bypass the next node.
- Free the memory of the node to be deleted.
Code Solution
-
1) Delete a node from linked list without head pointer in c
2) Delete a node from linked list without head node in c++
3) Delete a node from linked list without head pointer in java
4) Delete a node from linked list without head pointer in c#
5) Delete a node from linked list without head pointer in vb.net
6) Delete a node from linked list without head node in php
7) Delete a node from linked list without head pointer in python
8) Delete a node from linked list without head node in ruby
9) Delete a node from linked list without head pointer in scala
10) Delete a node from linked list without head pointer in swift
11) Delete a node from linked list without head in kotlin
12) Delete a node from linked list without head pointer in node js
13) Delete a node from linked list without head node in typescript
14) Delete a node from linked list without head pointer in golang
Time Complexity
The time complexity of deleting a node from a linked list without having a direct reference to the head is O(1). This is because you're essentially copying a value and updating a few pointers, which takes constant time.
Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.
New Comment