Find the middle of a given linked list

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);

Please do not post any spam link in the comment box😊

إرسال تعليق (0)
أحدث أقدم