The tortoise and hare algorithm is a classic algorithm to find the median of a linked list. It is named after the fable of the tortoise and the hare, where the tortoise wins by virtue of its steady pace.
The algorithm works as follows:
-
Use two pointers, one moves one step at a time, the other moves two steps at a time
-
When the fast pointer reaches the end of the linked list, the slow pointer is at the middle
-
If the length of the linked list is even, the slow pointer will be at the second middle
-
If the length of the linked list is odd, the slow pointer will be at the middle
The time and space complexity of the algorithm is as below -
Time complexity: O(n)
-
Space complexity: O(1)
//How to find mid point of a linked list in one pass of the linked list
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
this.length = 0;
}
push(value) {
const newNode = new Node(value);
if (this.head === null) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
this.tail = newNode;
}
this.length++;
return this;
}
findMid() {
let slow = this.head;
let fast = this.head;
while (fast !== null && fast.next !== null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
const list = new LinkedList();
list.push(1);
list.push(2);
list.push(3);
list.push(4);
list.push(5);
list.push(6);
list.push(7);
console.log(list.findMid().value);