如何用代码实现链表的排序功能

链表的排序有多种方法，以下是常用的两种方法：

1. 插入排序：对链表进行一次遍历，将每个节点插入到一个新的已排序链表中的正确位置。时间复杂度为O(n^2)。

2. 归并排序：先将链表分成两个子链表，对每个子链表进行排序，然后再将两个已排好序的子链表合并成一个有序链表。时间复杂度为O(nlogn)。

以下是用C++代码实现归并排序的示例：

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        ListNode* mid = slow->next;
        slow->next = nullptr;
        ListNode* left = sortList(head);
        ListNode* right = sortList(mid);
        return merge(left, right);
    }
    
    ListNode* merge(ListNode* l1, ListNode* l2) {
        if (!l1) {
            return l2;
        }
        if (!l2) {
            return l1;
        }
        if (l1->val < l2->val) {
            l1->next = merge(l1->next, l2);
            return l1;
        } else {
            l2->next = merge(l1, l2->next);
            return l2;
        }
    }
};