Removing Nodes with a Specific Value from a Linked List

Given the head node of a singly linked list and an integer value, the task is to delete all nodes whose value matches the given integer and return the new head of the list.

Example: Input: head = [1,2,6,3,4,5,6], val = 6 Output: [1,2,3,4,5]

Approach Using a Dummy Head Node

A common challenge is handling the case where the original head node itself needs to be removed. Using a dummy head node (or sentinel node) simplifies the logic by providing a stable starting point before the actual list.

Algorithm Steps:

1. Create Dummy Node: Instantiate a new node with an arbitrayr value (e.g., 0) and set its next pointer to the original head. This node acts as a placeholder.
2. Initialize Traversal Pointer: Set a pointer runner to point to the dummy node.
3. Iterate and Remove: Traverse the list using runner. While runner.next is not null:
   • Check if the value of runner.next equals the target val.
   • If it matches, skip that node by setting runner.next = runner.next.next. This effectively removes the node from the chain.
   • If it does not match, move the runner pointer forward: runner = runner.next.
4. Return New Head: After the loop, the dummy node's next pointer points to the new head of the modified list. Return dummy.next.

JavaScript Implementation:

function deleteNodes(head, targetVal) {
    const dummyHead = new ListNode(0);
    dummyHead.next = head;
    let runner = dummyHead;

    while (runner.next !== null) {
        if (runner.next.val === targetVal) {
            runner.next = runner.next.next;
        } else {
            runner = runner.next;
        }
    }
    return dummyHead.next;
}

---

Reversing a Singly Linked List

Given the head of a singly linked list, reverse the order of the nodes and return the new head.

Example: Input: head = [1,2,3,4,5] Output: [5,4,3,2,1]

In-Place Reversal Technique

Reversing a linked list efficiently involves redirecting the next pointers of each node without allocating extra memory for a new list.

Algorithm Steps:

1. Initialize Pointers:
   • prev: Initially null, as the new tail (original head) will point to null.
   • curr: Starts at the original head.
   • nextNode: A temporary variable to store the upcoming node.
2. Iterative Reversal: While curr is not null:
   • Store the next node: nextNode = curr.next.
   • Reverse the link: Set curr.next to point to prev.
   • Move pointers forward: Update prev to curr, and then update curr to nextNode.
3. New Head: When the loop finishes, curr is null, and prev is pointing to the last node processed, which is the new head of the reversed list.

JavaScript Implementation:

function reverseLinkedList(listHead) {
    if (listHead === null || listHead.next === null) {
        return listHead;
    }

    let prev = null;
    let curr = listHead;
    let nextNode = null;

    while (curr !== null) {
        nextNode = curr.next; // Save the next node
        curr.next = prev;     // Reverse the current node's pointer
        prev = curr;          // Move prev forward
        curr = nextNode;      // Move curr forward
    }
    // 'prev' is now the new head of the reversed list
    return prev;
}