解题思路：
\qquad 题目希望能在$O(nLogn)$时间复杂度内解决问题，满足这个条件的常用排序算法有：快速排序（Quick Sort）、归并排序（Merge Sort）和堆排序（Heap Sort）。

• 由于链表节点中的next指针，使节点按特定顺序链接。因而不适合频繁的移动元素，所以快速排序对于链表，用起来不是很方便。
• 堆排序，是利用堆这一数据结构的特点进行排序，将待排序元素存入栈，每次取堆顶的元素，自然是有序的。但要将链表节点存入栈，需要重写堆的排序方法，略微有些麻烦。
• 归并排序，将序列不断二分，对左右两个序列继续排序后，将返回的两个有序序列按顺序合并的排序算法。无论是二分，还是合并有序序列，都可以按照从左至右的顺序访问元素并完成，因此十分适合对链表排序。

\qquad 代码实现有几个注意的点：
\qquad 可以使用快慢指针，快速找到链表中间的节点；
\qquad 使用自定义节点做一个伪head，这样可以少判head为空的情况，返回时也要注意返回head->next;
\qquad 递归的终止条件，除了head为空之外，链表内只有一个元素的情况也要返回，不然会陷入死循环。

ListNode* sortList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* slow;
        ListNode* fast = head;
        while(fast != nullptr)
        {
            if(fast == head) slow = head;
            else slow = slow->next;
            if(fast->next == nullptr) fast = nullptr;
            else fast = fast->next->next;
        }

        if(slow != nullptr)
        {
            fast = sortList(slow->next);
            slow->next = nullptr;
        }
        else fast = sortList(nullptr);
        slow = sortList(head);

        ListNode* joined = new ListNode(0);
        ListNode* curr = joined;
        while(slow != nullptr || fast != nullptr)
        {
            if(slow != nullptr && fast != nullptr)
            {
                if(slow->val <= fast->val)
                {
                    curr->next = slow;
                    slow = slow->next;
                }
                else {
                    curr->next = fast;
                    fast = fast->next;
                }
                curr = curr->next;
            }
            else if(slow == nullptr)
            {
                curr->next = fast;
                break;
            }
            else
            {
                curr->next = slow;
                break;
            }
        }
        return joined->next;
    }