Given a node's reference within a doubly linked list, remove that node from the linked list while preserving the list's integrity.
You will only be given the node's reference, not the head of the list. It is guaranteed that the given node will not be the head of the list.
Input: head -> 1 <-> 3 <-> 5, node = 3
Output: head -> 1 <-> 5
Explanation: The referenced node with value 3 was removed.
Input: head -> 1 <-> 3 <-> 7, node = 7
Output: head -> 1 <-> 3
Explanation: The referenced node with value 7 was removed.
Input: head -> 1 <-> 5, node = 5
#include <bits/stdc++.h>
using namespace std;
// Definition of doubly linked list
struct ListNode
{
int val;
ListNode *next;
ListNode *prev;
ListNode()
{
val = 0;
next = NULL;
prev = NULL;
}
ListNode(int data1)
{
val = data1;
next = NULL;
prev = NULL;
}
ListNode(int data1, ListNode *next1, ListNode *prev1)
{
val = data1;
next = next1;
prev = prev1;
}
};
// Solution class
class Solution {
public:
/* Function to delete the given node
from doubly linked list */
void deleteGivenNode(ListNode* node) {
ListNode* prev = node->prev;
ListNode* front = node->next;
// Edge case if the given node is the tail node
if (front == nullptr) {
prev->next = nullptr;
node->prev = nullptr;
delete node;
return;
}
// Disconnect node
prev->next = front;
front->prev = prev;
// Set node's pointers to NULL
node->next = nullptr;
node->prev = nullptr;
// Free memory
delete node;
}
};
// Helper Function to convert an array to a doubly linked list
ListNode* arrayToLinkedList(vector<int> &nums) {
// If array is empty, return nullptr
if (nums.empty()) return nullptr;
// Create head node with first element of the array
ListNode* head = new ListNode(nums[0]);
// Initialize 'prev' to the head node
ListNode* prev = head;
for (int i=1; i < nums.size(); i++) {
// Create a new node
ListNode* temp = new ListNode(nums[i], nullptr, prev);
// Update 'next' pointer
prev->next = temp;
// Move 'prev' to newly created node
prev = temp;
}
// Return head
return head;
}
// Helper Function to print the linked list
void printLL(ListNode* head) {
while (head != NULL) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
int main() {
vector<int> nums = {1, 2, 3, 4, 5};
// Creating the doubly linked list from given array
ListNode* head = arrayToLinkedList(nums);
// Node to be deleted
ListNode* node = head-> next-> next;
// Print the Original list
cout << "Original List: ";
printLL(head);
// Create an instance of Solution class
Solution sol;
/* Function call to delete the given
node from the doubly linked list */
sol.deleteGivenNode(node);
// Print the Modified list
cout << "Modified list: ";
printLL(head);
return 0;
}
// Definition of doubly linked list
class ListNode {
int val;
ListNode next;
ListNode prev;
ListNode() {
val = 0;
next = null;
prev = null;
}
ListNode(int data1) {
val = data1;
next = null;
prev = null;
}
ListNode(int data1, ListNode next1, ListNode prev1) {
val = data1;
next = next1;
prev = prev1;
}
}
// Solution class
class Solution {
/* Function to delete the given node
from doubly linked list */
public void deleteGivenNode(ListNode node) {
ListNode prev = node.prev;
ListNode front = node.next;
// Edge case if the given node is the tail node
if (front == null) {
prev.next = null;
node.prev = null;
return;
}
// Disconnect node
prev.next = front;
front.prev = prev;
// Set node's pointers to null
node.next = null;
node.prev = null;
}
}
// Main class
class Main {
// Helper Function to convert an array to a doubly linked list
private static ListNode arrayToLinkedList(int[] nums) {
// If array is empty, return null
if (nums.length == 0) return null;
// Create head node with first element of the array
ListNode head = new ListNode(nums[0]);
// Initialize 'prev' to the head node
ListNode prev = head;
for (int i = 1; i < nums.length; i++) {
// Create a new node
ListNode temp = new ListNode(nums[i], null, prev);
// Update 'next' pointer
prev.next = temp;
// Move 'prev' to newly created node
prev = temp;
}
// Return head
return head;
}
// Helper Function to print the linked list
private static void printLL(ListNode head) {
while (head != null) {
System.out.print(head.val + " ");
head = head.next;
}
System.out.println();
}
// main method
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
// Creating the doubly linked list from given array
ListNode head = arrayToLinkedList(nums);
// Node to be deleted
ListNode node = head.next.next;
// Print the Original list
System.out.print("Original List: ");
printLL(head);
// Create an instance of Solution class
Solution sol = new Solution();
/* Function call to delete the given
node from the doubly linked list */
sol.deleteGivenNode(node);
// Print the Modified list
System.out.print("Modified list: ");
printLL(head);
}
}
# Definition of doubly linked list
class ListNode:
def __init__(self, data1=0, next1=None, prev1=None):
self.val = data1
self.next = next1
self.prev = prev1
# Solution class
class Solution:
''' Function to delete the given node
from doubly linked list '''
def deleteGivenNode(self, node):
prev = node.prev
front = node.next
# Edge case if the given node is the tail node
if front is None:
prev.next = None
node.prev = None
return
# Disconnect node
prev.next = front
front.prev = prev
# Set node's pointers to None
node.next = None
node.prev = None
# Helper Function to convert an array to a doubly linked list
def arrayToLinkedList(nums):
# If array is empty, return None
if not nums:
return None
# Create head node with first element of the array
head = ListNode(nums[0])
# Initialize 'prev' to the head node
prev = head
for i in range(1, len(nums)):
# Create a new node
temp = ListNode(nums[i], None, prev)
# Update 'next' pointer
prev.next = temp
# Move 'prev' to newly created node
prev = temp
# Return head
return head
# Helper Function to print the linked list
def printLL(head):
while head is not None:
print(head.val, end=" ")
head = head.next
print()
if __name__ == "__main__":
nums = [1, 2, 3, 4, 5]
# Creating the doubly linked list from given array
head = arrayToLinkedList(nums)
# Node to be deleted
node = head.next.next
# Print the Original list
print("Original List: ", end="")
printLL(head)
# Create an instance of Solution class
sol = Solution()
''' Function call to delete the given
node from the doubly linked list '''
sol.deleteGivenNode(node)
# Print the Modified list
print("Modified list: ", end="")
printLL(head)
// Definition of doubly linked list
class ListNode {
constructor(data1 = 0, next1 = null, prev1 = null) {
this.val = data1;
this.next = next1;
this.prev = prev1;
}
}
// Solution class
class Solution {
/* Function to delete the given node
from doubly linked list */
deleteGivenNode(node) {
let prev = node.prev;
let front = node.next;
// Edge case if the given node is the tail node
if (front === null) {
prev.next = null;
node.prev = null;
return;
}
// Disconnect node
prev.next = front;
front.prev = prev;
// Set node's pointers to null
node.next = null;
node.prev = null;
}
}
// Helper Function to convert an array to a doubly linked list
function arrayToLinkedList(nums) {
// If array is empty, return null
if (nums.length === 0) return null;
// Create head node with first element of the array
let head = new ListNode(nums[0]);
// Initialize 'prev' to the head node
let prev = head;
for (let i = 1; i < nums.length; i++) {
// Create a new node
let temp = new ListNode(nums[i], null, prev);
// Update 'next' pointer
prev.next = temp;
// Move 'prev' to newly created node
prev = temp;
}
// Return head
return head;
}
// Helper Function to print the linked list
function printLL(head) {
while (head !== null) {
process.stdout.write(head.val + " ");
head = head.next;
}
console.log();
}
const main = () => {
const nums = [1, 2, 3, 4, 5];
// Creating the doubly linked list from given array
let head = arrayToLinkedList(nums);
// Node to be deleted
let node = head.next.next;
// Print the Original list
console.log("Original List: ");
printLL(head);
// Create an instance of Solution class
let sol = new Solution();
/* Function call to delete the given
node from the doubly linked list */
sol.deleteGivenNode(node);
// Print the Modified list
console.log("Modified list: ");
printLL(head);
}
main();
Q: How does this differ from deleting a node when the head is available?
A: Without the head, we cannot traverse backward or forward for extra checks; we must rely only on the given node’s prev and next pointers.
Q: How would you modify this for a circular doubly linked list?
A: Update the previous node’s next and next node’s prev, ensuring circularity is maintained.
Q: What if the given node was part of a sorted doubly linked list?
A: Deletion remains O(1), but ensuring sorting requires extra insert operations elsewhere.