给定一个节点数为n的无序单链表，对其按升序排序。生成c++代码，class Solution { public: /** * * @param head ListNode类 the head node * @return ListNode类 / ListNode sortInList(ListNode* head) { // write code here } };

可以使用归并排序来对无序单链表进行排序。具体实现步骤如下：

1. 如果链表为空或只有一个节点，则无需排序，直接返回头节点。

2. 使用快慢指针法将链表分成两个部分，即将链表从中间断开，分成左右两个部分。

3. 对左右两个部分分别进行递归排序。

4. 将左右两个部分合并成一个有序链表。

5. 返回合并后的链表头节点。

以下是对应的C++代码实现：

class Solution {
public:
ListNode* sortInList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return head;
}
ListNode* slow = head;
ListNode* fast = head->next;
while (fast != nullptr && fast->next != nullptr) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* right = sortInList(slow->next);
slow->next = nullptr;
ListNode* left = sortInList(head);
return merge(left, right);
}
private:
ListNode* merge(ListNode* left, ListNode* right) {
ListNode dummy(0);
ListNode* tail = &dummy;
while (left != nullptr && right != nullptr) {
if (left->val < right->val) {
tail->next = left;
left = left->next;
} else {
tail->next = right;
right = right->next;
}
tail = tail->next;
}
if (left != nullptr) {
tail->next = left;
} else {
tail->next = right;
}
return dummy.next;
}
};