Find middle node of linked list
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131
class Node {
constructor(value){
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor(value) {
const newNode = new Node(value);
this.head = newNode;
this.tail = this.head;
}
printList() {
let temp = this.head;
while (temp !== null) {
console.log(temp.value);
temp = temp.next;
}
}
getHead() {
if (this.head === null) {
console.log("Head: null");
} else {
console.log("Head: " + this.head.value);
}
}
getTail() {
if (this.tail === null) {
console.log("Tail: null");
} else {
console.log("Tail: " + this.tail.value);
}
}
makeEmpty() {
this.head = null;
this.tail = null;
this.length = 0;
}
push(value) {
const newNode = new Node(value);
if (!this.head) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
}
findMiddleNode(){
// if(!this.head) return undefined;
// let count = 1;
// let temp = this.head;
// while(temp.next){
// ++count;
// temp = temp.next;
// }
// count = Math.floor(count/2)+1;
// for(let i=0;i<count;i++){
// temp = this.head;
// this.head = this.head.next;
// }
// return temp;
//tortoise & hare approach
let slow = this.head;
let fast = this.head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
let myLinkedList = new LinkedList(1);
myLinkedList.push(2);
myLinkedList.push(3);
myLinkedList.push(4);
myLinkedList.push(5);
console.log("Original list:");
myLinkedList.printList();
const middleNode = myLinkedList.findMiddleNode();
console.log(`\nMiddle node value: ${middleNode.value}`);
// Create a new list with an even number of elements
let myLinkedList2 = new LinkedList(1);
myLinkedList2.push(2);
myLinkedList2.push(3);
myLinkedList2.push(4);
myLinkedList2.push(5);
myLinkedList2.push(6);
console.log("\nOriginal list 2:");
myLinkedList2.printList();
const middleNode2 = myLinkedList2.findMiddleNode();
console.log(`\nMiddle node value of list 2: ${middleNode2.value}`);
/*
EXPECTED OUTPUT:
----------------
Original list:
1
2
3
4
5
Middle node value: 3
Original list 2:
1
2
3
4
5
6
Middle node value of list 2: 4
*/
JavaScript
INFO