linked-list.js

linked-list.js

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
        this.length = 1
    }

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

    getLength() {
        console.log("Length: " + this.length)
    }

    // O(1)
    push(value) {
        const newNode = new Node(value)
        if (!this.head) {
            this.head = newNode
            this.tail = newNode
        } else {
            this.tail.next = newNode
            this.tail = newNode
        }
        this.length++
        return this
    }

    // O(n)
    pop() {
        // No item to pop
        if (!this.head)
            return undefined

        let temp = this.head
        let pre = this.head
        while (temp.next) {
            pre = temp
            temp = temp.next
        }
        this.tail = pre
        this.tail.next = null
        this.length--

        // Last item was popped
        if (this.length === 0) {
            this.head = null
            this.tail = null
        }

        return temp
    }

    // O(1)
    unshift(value) {
        const newNode = new Node(value)
        if (!this.head) {
            this.head = newNode
            this.tail = newNode
        } else {
            newNode.next = this.head
            this.head = newNode
        }
        this.length++
        return this
    }

    // O(1)
    shift() {
        // No item to shift
        if (!this.head)
            return undefined

        let temp = this.head
        this.head = this.head.next
        temp.next = null
        this.length--

        // Last item was shifted
        if (this.length === 0) {
            this.tail = null
        }

        return temp
    }

    // O(n)
    get(index) {
        if (index < 0 || index >= this.length) {
            return undefined
        }
        let temp = this.head
        for (let i = 0; i < index; i++) {
            temp = temp.next
        }
        return temp
    }

    // O(n)
    set(index, value) {
        let temp = this.get(index)
        if (temp) {
            temp.value = value
            return true
        }
        return false
    }

    // O(n)
    insert(index, value) {
        if (index < 0 || index > this.length)
            return false
        // Out of range
        if (index === 0)
            return this.unshift(value)
        // Start
        if (index === this.length)
            return this.push(value)
        // End

        const newNode = new Node(value)
        const temp = this.get(index - 1)

        newNode.next = temp.next
        temp.next = newNode
        this.length++
        return true
    }

    // O(n)
    remove(index) {
        if (index === 0)
            return this.shift()
        if (index === this.length - 1)
            return this.pop()
        if (index < 0 || index >= this.length)
            return undefined

        const before = this.get(index - 1)
        const temp = before.next

        before.next = temp.next
        temp.next = null
        this.length--
        return temp
    }

    // O(n)
    reverse() {
        let temp = this.head
        this.head = this.tail
        this.tail = temp
        let next = temp.next
        let prev = null
        for (let i = 0; i < this.length; i++) {
            next = temp.next
            temp.next = prev
            prev = temp
            temp = next
        }
        return this
    }

    findMiddleNode() {
        // Initialize slow and fast pointers at head
        let slow = this.head
        let fast = this.head
        // Iterate through the list
        while (fast !== null && fast.next !== null) {
            // Move slow pointer one step
            slow = slow.next
            // Move fast pointer two steps
            fast = fast.next.next
        }
        // Return middle node when fast reaches end
        return slow
    }

    // The "tortoise and hare" algorithm works by
    // having two pointers move at different speeds
    // through the linked list. If there is a loop, 
    // the faster pointer (the hare) will eventually
    // catch up to the slower pointer (the tortoise)
    // inside the loop. If there is no loop, the faster
    // pointer will reach the end of the list.
    hasLoop() {
        // Initialize slow and fast pointers at head
        let slow = this.head
        let fast = this.head
        // Iterate through the list
        while (fast !== null && fast.next != null) {
            // Move slow pointer one step
            slow = slow.next
            // Move fast pointer two steps
            fast = fast.next.next
            // If slow and fast pointers meet, loop exists
            if (slow === fast) {
                return true;
            }
        }
        // If no loop is found, return false
        return false
    }

    // The two-pointer technique used in this function
    // ensures that the linked list is traversed only
    // once, making the algorithm efficient with a time
    // complexity of O(n), where n is the number of nodes
    // in the list
    findKthFromEnd(k) {
        // Initialize slow and fast
        let slow = this.head
        let fast = this.head
        // Move faster pointer k steps ahead
        for (let i = 0; i < k; i++) {
            // If fast reaches null, k is out of range
            if (fast === null) {
                return null
            }
            fast = fast.next
        }
        // Iterate until fast reaches the end
        while (fast != null) {
            // Move slow and fast pointers one step
            slow = slow.next
            fast = fast.next
        }
        // When fast reaches end, slow is at kth from end
        return slow
    }
}

let myLinkedList = new LinkedList(1);
myLinkedList.push(2);
myLinkedList.push(3);
myLinkedList.push(4);
myLinkedList.push(5);
myLinkedList.push(6);
// myLinkedList.tail.next = myLinkedList.head.next;

myLinkedList.findKthFromEnd(3)