How to use Two-pointer approach In Javascript
In this approach we use two pointers, a slow pointer and a fast pointer initialized to the head of the list. The fast pointer moves two nodes at a time while the slow pointer moves one node at a time. When the fast pointer reaches the end of the list the slow pointer will be pointing to the middle node. We then delete the middle node by adjusting the pointers of the previous and next nodes of the middle node to skip over it.
Example: The example below shows the demonstration to delete middle of doubly linked list using two-pointer approach.
class Node {
constructor(data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
}
// Method to print the list
printList() {
let current = this.head;
while (current !== null) {
process.stdout.write(`${current.data} <-> `);
current = current.next;
}
process.stdout.write("null\n");
}
// Two-pointer approach
deleteMiddleTwoPointer() {
let slow = this.head;
let fast = this.head;
while (fast && fast.next && fast.next.next) {
slow = slow.next;
fast = fast.next.next;
}
let middle = slow;
if (middle === this.head) {
this.head = middle.next;
} else {
middle.prev.next = middle.next;
}
if (middle === this.tail) {
this.tail = middle.prev;
} else {
middle.next.prev = middle.prev;
}
middle = null;
}
}
// Example usage
let list = new DoublyLinkedList();
list.head = new Node(1);
list.head.next = new Node(2);
list.head.next.prev = list.head;
list.head.next.next = new Node(3);
list.head.next.next.prev = list.head.next;
list.head.next.next.next = new Node(4);
list.head.next.next.next.prev = list.head.next.next;
list.head.next.next.next.next = new Node(5);
list.head.next.next.next.next.prev = list.head.next.next.next;
list.tail = list.head.next.next.next.next;
console.log("Before deletion:");
list.printList();
list.deleteMiddleTwoPointer();
console.log("After deletion:");
list.printList();
Output
Before deletion: 1 <-> 2 <-> 3 <-> 4 <-> 5 <-> null After deletion: 1 <-> 2 <-> 4 <-> 5 <-> null
Time Complexity: O(n)
Space complexity: O(1)
JavaScript Program to Delete Middle of Doubly Linked List
We are given a doubly linked list and we have to write a JavaScript program to delete the middle node of the list and print the newly formed linked list after the deletion.
Example:
Input: 1 <-> 2 <-> 3 <-> 4 <-> 5
Output: 1 <-> 2 <-> 4 <-> 5
Below are the different approaches to delete the middle of a doubly linked list:
Table of Content
- Using Two-pointer approach
- Using Traversal Method
Contact Us