Delete node in Doubly Linked List

Given a doubly Linked list and a position. The task is to delete a node from a given position (position starts from 1) in a doubly linked list and return the head of the doubly Linked list.

Examples:

Input: LinkedList = 1 <--> 3 <--> 4, x = 3
Output: 1 3 
Explanation: 
After deleting the node at position 3 (position starts from 1),the linked list will be now as 1 <--> 3.
Input: LinkedList = 1 <--> 5 <--> 2 <--> 9, x = 1
Output: 5 2 9
Explanation:

Expected Time Complexity: O(n)
Expected Auxilliary Space: O(1)

Constraints:
2 <= size of the linked list(n) <= 105
1 <= x <= n
1 <= node.data <= 109


Approach 01:

class Solution {
  public:
    Node* deleteNode(Node* head, int position) {
        // If the position is the head node
        if (position == 1) return head->next;
        
        // Edge cases
        if (head == nullptr || position <= 0) return head;
        
        Node* current_node = head;
        Node* previous_node = nullptr;
        
        // Traverse to the node at the given position
        for (int i = 1; i < position; ++i) {
            previous_node = current_node;
            current_node = current_node->next;
        }
        
        // Unlink the node from the list
        previous_node->next = current_node->next;
        if (current_node->next)
            current_node->next->prev = previous_node;
        
        // Delete the node
        delete current_node;
        
        return head;
    }
};
class Solution:
    def delete_node(self, head, position):
        # If the position is the head node
        if position == 1:
            head = head.next
            if head:
                head.prev = None
            return head
        
        # Edge cases
        if head is None or position <= 0:
            return head
        
        current_node = head
        previous_node = None
        
        # Traverse to the node at the given position
        for i in range(1, position):
            previous_node = current_node
            current_node = current_node.next
        
        # Unlink the node from the list
        previous_node.next = current_node.next
        if current_node.next:
            current_node.next.prev = previous_node
        
        # Delete the node
        del current_node
        
        return head

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top