Eliminating Target Values from a Linked List

Modifying a linked list in-place by adjusting the next pointer of the preceding node works well for intermediate and tail nodes. However, this logic breaks when the target value resides in the head node, as there is no prior node to update. Introducing a sentinel (dummy) head node resolves this by providing a consistent predecessor for every element, including the original head. Upon completion, the new head is returned via sentinel.next.

function eliminateNodes(listHead, targetVal) {
    const sentinel = new ListNode(0, listHead);
    let current = sentinel;
    while (current.next !== null) {
        if (current.next.val === targetVal) {
            current.next = current.next.next;
        } else {
            current = current.next;
        }
    }
    return sentinel.next;
}

Constructing a Custom Linked List

Implementing a linked list from scratch requires managing node pointers for various operations: retrieval, insertion, and deletion. A sentinel head node standardizes insertion and deletion logic, preventing null pointer exceptions when operating near the beginning of the sequence. Maintaining a length variable allows for quick boundary checks before traversing.

class CustomLinkedList {
    constructor() {
        this.length = 0;
        this.sentinel = { value: 0, next: null };
    }

    traverseTo(index) {
        let ptr = this.sentinel;
        for (let i = 0; i <= index; i++) {
            ptr = ptr.next;
        }
        return ptr;
    }

    retrieve(index) {
        if (index < 0 || index >= this.length) return -1;
        return this.traverseTo(index).value;
    }

    insertAtFront(val) {
        this.insertAt(0, val);
    }

    appendAtEnd(val) {
        this.insertAt(this.length, val);
    }

    insertAt(index, val) {
        if (index < 0 || index > this.length) return;
        let predecessor = this.sentinel;
        for (let i = 0; i < index; i++) {
            predecessor = predecessor.next;
        }
        const newNode = { value: val, next: predecessor.next };
        predecessor.next = newNode;
        this.length++;
    }

    eraseAt(index) {
        if (index < 0 || index >= this.length) return;
        let predecessor = this.sentinel;
        for (let i = 0; i < index; i++) {
            predecessor = predecessor.next;
        }
        predecessor.next = predecessor.next.next;
        this.length--;
    }
}

Reversing a Linked List

Reversing a singly linked list can be achieved through iterative pointer manipulation or recursion.

Iterative Pointer Reversal

Initialize a previous pointer as null and a current pointer at the head. During each iteration, temporarily store the next node, redirect the current node's pointer to the previous node, then advance both pointers. Once current reaches the end, previous will point to the new head.

function invertListIterative(head) {
    let previous = null;
    let current = head;
    while (current !== null) {
        let nextTemp = current.next;
        current.next = previous;
        previous = current;
        current = nextTemp;
    }
    return previous;
}

Recursive Approach

The recursive method delegates the reversal by passing the previous and current nodes down the call stack. Each recursive call processes the current link reversal before moving forward. The base case returns the new head when current becomes null.

function invertListRecursive(head) {
    return reverseRecursive(null, head);
}

function reverseRecursive(prev, curr) {
    if (curr === null) return prev;
    let nextNode = curr.next;
    curr.next = prev;
    return reverseRecursive(curr, nextNode);
}