Given the head of a linked list, return the list after sorting it in ascending order.

&nbsp;
Example 1:

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


Example 2:

Input: head = [-1,5,3,4,0]
Output: [-1,0,3,4,5]


Example 3:

Input: head = []
Output: []


&nbsp;
Constraints:


	The number of nodes in the list is in the range [0, 5 * 104].
	-105 &lt;= Node.val &lt;= 105


&nbsp;
Follow up: Can you sort the linked list in O(n logn) time and O(1) memory (i.e. constant space)?

class Solution:
    def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        store = []
        curr = head
        while curr:
            store.append(curr.val)
            curr = curr.next
        store.sort()
        dummyNode = ListNode(0)
        temp = dummyNode
        
        for i in store:
            x = ListNode(val = i)
            temp.next = x
            temp = x
        return dummyNode.next
/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode mid = middle(head);

        ListNode left = sortList(head);
        ListNode right = sortList(mid);

        return mergeTwoLists(left, right);
    }
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode();
        ListNode tail = head;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                tail.next = list1;
                list1 = list1.next;
                tail = tail.next;
            } else {
                tail.next = list2;
                list2 = list2.next;
                tail = tail.next;
            }
        }

        tail.next = (list1 != null) ? list1 : list2;

        return head.next;
    }

    public ListNode middle(ListNode head) {
        ListNode midprev = null;
        while (head != null && head.next != null) {
            midprev = (midprev == null) ? head : midprev.next;
            head = head.next.next;
        }
        ListNode mid = midprev.next;
        midprev.next = null;
        return mid;
    }
}
                            // Please upvote if it helps
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        //If List Contain a Single or 0 Node
        if(head == NULL || head ->next == NULL)
            return head;

        ListNode *temp = NULL;
        ListNode *slow = head;
        ListNode *fast = head;

        // 2 pointer appraoach / turtle-hare Algorithm (Finding the middle element)
        while(fast != NULL && fast -> next != NULL)
        {
            temp = slow;
            slow = slow->next; //slow increment by 1
            fast = fast ->next ->next; //fast incremented by 2

        }
        temp -> next = NULL; //end of first left half

        ListNode* l1 = sortList(head); //left half recursive call
        ListNode* l2 = sortList(slow); //right half recursive call

        return mergelist(l1, l2); //mergelist Function call

    }

    //MergeSort Function O(n*logn)
    ListNode* mergelist(ListNode *l1, ListNode *l2)
    {
        ListNode *ptr = new ListNode(0);
        ListNode *curr = ptr;

        while(l1 != NULL && l2 != NULL)
        {
            if(l1->val <= l2->val)
            {
                curr -> next = l1;
                l1 = l1 -> next;
            }
            else
            {
                curr -> next = l2;
                l2 = l2 -> next;
            }

        curr = curr ->next;

        }

        //for unqual length linked list

        if(l1 != NULL)
        {
            curr -> next = l1;
            l1 = l1->next;
        }

        if(l2 != NULL)
        {
            curr -> next = l2;
            l2 = l2 ->next;
        }

        return ptr->next;
    }
};
function getListSize(head) {
    let curr = head;
    let size = 0;

    while(curr !== null) {
        size += 1;

        curr = curr.next;
    }

    return size;
}

function splitInHalf(head, n) {
    let node1 = head;
    let curr = head;

    for (let i = 0; i < Math.floor(n / 2) - 1; i++) {
        curr = curr.next;
    }

    const node2 = curr.next;
    curr.next = null;

    return [
        node1,
        Math.floor(n / 2),
        node2,
        n - Math.floor(n / 2),
    ]
}

function merge(head1, head2) {
    if (head1.val > head2.val) {
        return merge(head2, head1)
    }

    const head = head1;
    let curr = head1;

    let runner1 = curr.next;
    let runner2 = head2;

    while (runner1 !== null || runner2 !== null) {
        const runner1Value = runner1 ? runner1.val : Infinity;
        const runner2Value = runner2 ? runner2.val : Infinity;

        if (runner1Value < runner2Value) {
            curr.next = runner1;
            runner1 = runner1.next;
        } else {
            curr.next = runner2;
            runner2 = runner2.next;
        }

        curr = curr.next;
    }

    curr.next = null;
    return head;
}

var sortList = function(head) {
    const size = getListSize(head);

    function mergeSort(node, n) {
        if (n <= 1) {
            return node;
        }

        const [node1, n1, node2, n2] = splitInHalf(node, n);
        const [merged1, merged2] = [mergeSort(node1, n1), mergeSort(node2, n2)];

        return merge(merged1, merged2);
    }

    return mergeSort(head, size);
};
Sort List