1. Merge 2 Sorted Lists

ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        ListNode *head = NULL;
        ListNode *tail = NULL;
        if (!list1)
            return list2;
        if (!list2)
            return list1;

        while (list1 && list2)
        {
            ListNode *temp = NULL;
            if (list1->val <= list2->val)
            {
                temp = list1;
                list1 = list1->next;
            }
            else
            {
                temp = list2;
                list2 = list2->next;
            }
            if (!head)
                head = tail = temp;
            else
            {
                tail->next = temp;
                tail = temp;
            }
        }

        if (list1)
        {
            if (!head)
                head = list1;
            else
                tail->next = list1;
        }
        if (list2)
        {
            if (!head)
                head = list2;
            else
                tail->next = list2;
        }
        return head;
    }

2. Merge K Sorted Lists

ListNode *mergeKLists(vector<ListNode *> &lists)
    {
        if (lists.size() == 0)
            return NULL;
        ListNode *head = NULL;
        ListNode *tail = NULL;
        priority_queue<pair<int, ListNode *>, vector<pair<int, ListNode *>>, greater<>> pq;

        int k = lists.size();
        for (auto link : lists)
            if (link)
                pq.push({link->val, link});

        while (!pq.empty())
        {
            auto [val, node] = pq.top();
            pq.pop();
            if (head == NULL)
            {
                head = node;
                tail = node;
            }
            else
            {
                tail->next = node;
                tail = tail->next;
            }

            if (node->next)
            {
                pq.push({node->next->val, node->next});
            }
        }

        return head;
    }

3. Sort Linked List

 ListNode *sortList(ListNode *head)
    {
        if (!head || !head->next)
            return head;

        ListNode *partition = middleOfLinkedList(head); //tortoise hare

        ListNode *right = partition->next;
        ListNode *left = head;
        partition->next = NULL;

        left = sortList(left);
        right = sortList(right);

        return mergeTwoSortedLists(left, right); //previous code same
    }