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:
-
C++
-
Python
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