3839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

class Solution {
    // Function to merge two sorted linked lists
    mergeTwoSortedLinkedLists(list1, list2) {
        // Create dummy node to serve as head of merged list
        let dummyNode = new ListNode(-1);
        let temp = dummyNode;

        // Traverse both lists simultaneously
        while (list1 !== null && list2 !== null) {
            /*Compare elements of both lists 
            and link the smaller node 
            to the merged list*/
            if (list1.val <= list2.val) {
                temp.next = list1;
                list1 = list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            // Move the temporary pointer to the next node
            temp = temp.next; 
        }

        /*If any list still has 
        remaining elements append 
        them to the merged list*/
        if (list1 !== null) {
            temp.next = list1;
        } else {
            temp.next = list2;
        }
        // Return the merged list starting 
        // from the next of the dummy node
        return dummyNode.next;
    }

    // Function to find the middle of a linked list
    findMiddle(head) {
        // If the list is empty or has only one node, 
        // the middle is the head itself
        if (head === null || head.next === null) {
            return head;
        }

        // Initializing slow and fast pointers
        let slow = head;
        let fast = head.next;

       /* Move the fast pointer twice as fast as the slow pointer
        When the fast pointer reaches the end, the slow pointer 
        will be at the middle*/
        while (fast !== null && fast.next !== null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // Function to perform merge sort on a linked list
    sortList(head) {
        /*Base case: if the list is empty or has only one node, 
        it is already sorted, so return the head*/
        if (head === null || head.next === null) {
            return head;
        }
        
        // Find middle of list using findMiddle function
        let middle = this.findMiddle(head);
        
        // Divide the list into two halves
        let right = middle.next;
        middle.next = null;
        let left = head;
        
        // Recursively sort left and right halves
        left = this.sortList(left);
        right = this.sortList(right);
        
        // Merge the sorted halves using the 
        // mergeTwoSortedLinkedLists function
        return this.merge