Merge Two Sorted Lists - JS Solution

Solution code

const LIST1 = 'list1_head', LIST1_COLOR = 'goldenrod';
const LIST2 = 'list2_head', LIST2_COLOR = 'deepskyblue';
const DUMMY = 'dummy', DUMMY_COLOR = 'lightgray';

function visMainFunction(inputList1, inputList2) {
    initClassProperties();
    explanationAndColorSchemaNotifications();
    let list1 = convertInputToLinkedList(inputList1);
    let list2 = convertInputToLinkedList(inputList2);

    const dummy = new ListNode(0);
    let mergedListTail = dummy;

    startBatch();
    const listVis1 = new VisLinkedList(list1, { dataPropName: 'val' }).options({ label: 'list1' });
    const listVis2 = new VisLinkedList(list2, { dataPropName: 'val' }).options({ label: 'list2' });
    const mergedVis = new VisLinkedList(dummy, { dataPropName: 'val' }).options({ label: 'mergedList' });

    mergedVis.makeVisManagerForNode(dummy).addClass(DUMMY);
    listVis1.visManager.addClass(LIST1);
    listVis2.visManager.addClass(LIST2);
    endBatch();

    notification(`
        🚦 <b>Start merge:</b> Create a ${makeColoredSpan('dummy node', DUMMY_COLOR)}, 
        which serves as a <b>dummy head</b> for the merged list — its <code>next</code> pointer will always point to 
        the current real head of the merged list. 
        This simplifies edge cases and pointer handling.<br>
        Initialize <code>mergedListTail</code> to this dummy node 
        (initially, the merged list contains no real nodes — only the dummy head).<br>
        Then, at each step: compare the <b>head</b> of ${makeColoredSpan('list1', LIST1_COLOR)} 
        with the <b>head</b> of ${makeColoredSpan('list2', LIST2_COLOR)}, 
        attach the smaller node after <code>mergedListTail</code>, 
        advance that list’s head, and move <code>mergedListTail</code> forward.
    `);

    while (list1 && list2) {
        startPartialBatch();
        let nodeClass;

        if (list1.val <= list2.val) {
            // REPLACE inside the (list1.val <= list2.val) branch
            notification(`
                ✅ Head of ${makeColoredSpan('list1', LIST1_COLOR)} (${list1.val}) ≤ head of ${makeColoredSpan('list2', LIST2_COLOR)} (${list2.val}) — attach from ${makeColoredSpan('list1', LIST1_COLOR)}.<br>
                Link it after <code>mergedListTail</code>, then advance ${makeColoredSpan('list1', LIST1_COLOR)} to its next head.
            `);
            mergedListTail.next = list1;
            list1 = list1.next;
            nodeClass = LIST1;
        } else {
            // REPLACE inside the (else) branch (list2 < list1)
            notification(`
                ✅ Head of ${makeColoredSpan('list2', LIST2_COLOR)} (${list2.val}) < head of ${makeColoredSpan('list1', LIST1_COLOR)} (${list1.val}) — attach from ${makeColoredSpan('list2', LIST2_COLOR)}.<br>
                Link it after <code>mergedListTail</code>, then advance ${makeColoredSpan('list2', LIST2_COLOR)} to its next head.
            `);

            mergedListTail.next = list2;
            list2 = list2.next;
            nodeClass = LIST2;
        }

        notification(`
            Move <code>mergedListTail</code> forward to the new tail of the merged list 
            (the node that was just attached from ${makeColoredSpan('list1', LIST1_COLOR)} or ${makeColoredSpan('list2', LIST2_COLOR)}).
        `);
        mergedListTail = mergedListTail.next;
        mergedVis.makeVisManagerForNode(mergedListTail).addClass(nodeClass);
        endBatch();
    }

    startPartialBatch();
    if (list1 || list2) {
        const remaining = list1 || list2;
        notification(`
            📌 One list is exhausted.<br> 
            Append the remaining nodes from the <b>other</b> list (${list1 ? makeColoredSpan('list2', LIST2_COLOR) : makeColoredSpan('list1', LIST1_COLOR)}) — 
            from its current <b>head</b> all the way to its <b>tail</b> — directly to the end of the merged list.<br><br>
            Simply set <code>mergedListTail.next = remaining</code>; this connects all remaining nodes in one step, 
            since they are already linked together in sorted order.
        `);
        mergedListTail.next = remaining;
        highlightRemaining(mergedVis, remaining, list1 ? LIST1 : LIST2);
    }
    endBatch();

    notification(`
        🏁 <b>Merge Complete!</b><br>
        The merged list is now fully constructed. The actual result begins at <code>dummy.next</code>, 
        which points to the real head of the merged list. 
        The <code>dummy</code> node itself served only as a helper to simplify link management 
        and is <b>not</b> part of the final output.
    `);
    return dummy.next;
}

function initClassProperties() {
    setClassProperties(LIST1, {
        backgroundColor: LIST1_COLOR
    });

    setClassProperties(LIST2, {
        backgroundColor: LIST2_COLOR
    });

    setClassProperties(DUMMY, {
        backgroundColor: DUMMY_COLOR
    });
}

function highlightRemaining(list, remaining, className) {
    let current = remaining;
    startBatch();
    while (current) {
        list.makeVisManagerForNode(current).addClass(className);
        current = current.next;
    }
    endBatch();
}

function convertInputToLinkedList(arr) {
    const dummy = new ListNode(0);
    let current = dummy;
    for (const val of arr) {
        current.next = new ListNode(val);
        current = current.next;
    }
    return dummy.next;
}

function ListNode(val, next) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
}

function explanationAndColorSchemaNotifications() {
  explanationNotification();
  notification(`
    🎨 <b>Color Schema</b><br><br>
    <b>${makeColoredSpan('list1 nodes', LIST1_COLOR)}</b> — nodes that originate from <b>list1</b> (highlighted when attached to the merged list).<br>
    <b>${makeColoredSpan('list2 nodes', LIST2_COLOR)}</b> — nodes that originate from <b>list2</b> (highlighted when attached to the merged list).<br>
    <b>${makeColoredSpan('dummy head', DUMMY_COLOR)}</b> — the helper <b>dummy</b> node used to simplify head handling; not part of the final output.<br><br>
    🕓 <b>Note:</b> Nodes in the merged list without a background color are there because they are <b>attached</b> 
    to the current <code>mergedListTail</code>, but their <b>final positions</b> in the merged order are <b>not yet fixed</b> — 
    they will settle into their correct sorted positions as the merge progresses.
  `);
}