方法一：转为数组，对数组排序

方法二：对链表插入排序，时间复杂度$O(n^2)$

直接插入排序：从下标为1的数开始，在前面已经排好序的序列中找到要插入的位置，直到整个序列有序。

struct ListNode* insertionSortList(struct ListNode* head) {
    struct ListNode *hair = (struct ListNode *)malloc(sizeof(struct ListNode));
    hair->next = head;
    struct ListNode *tail = head;
    while(tail->next != NULL){
        struct ListNode *pre = hair;
        while(pre != tail && pre->next->val <= tail->next->val)pre = pre->next;
        if(pre != tail){
            struct ListNode *curr = tail->next;
            tail->next = curr->next;
            curr->next = pre->next;
            pre->next = curr;
        } 
        else tail = tail->next;
    }
    return hair->next;
}

方法三：对链表归并排序，时间复杂度$O(nlogn)$，空间复杂度$O(1)$

数组的归并排序空间复杂度$O(n)$，而链表归并排序可以做到空间复杂度$O(1)$。单纯的链表不可以进行快速排序、堆排序、折半插入排序、希尔排序。链表可以直接插入排序、冒泡排序、简单选择排序、归并排序、基数排序。

用size表示每次需要排序的子链表的长度，初始时size=1。每次将链表拆分成若干个长度为size的子链表（最后一个子链表的长度可以小于size），按照每两个子链表一组进行合并。合并两个子链表使用「21. 合并两个有序链表」的做法。

struct ListNode* merge(struct ListNode* a, struct ListNode *b){
    struct ListNode *res = (struct ListNode *)malloc(sizeof(struct ListNode)), *curr = res;
    while(a != NULL && b != NULL){
        if(a->val < b->val)curr->next = a, a = a->next;
        else curr->next = b, b = b->next;
        curr = curr->next;
    }
    if(a != NULL)curr->next = a;
    else curr->next = b;

    return res->next;
}
struct ListNode* mergeSort(struct ListNode* head){
    int tot = 0;struct ListNode *ptr = head;
    while(ptr != NULL){
        ptr = ptr->next;
        tot++;
    }
    struct ListNode *hair = (struct ListNode *)malloc(sizeof(struct ListNode));
    hair->next = head;
    for (int size = 1; size < tot; size *= 2) {
        struct ListNode *pre = hair, *curr = pre->next;
        while (curr != NULL) {
            struct ListNode* head1 = curr;
            for (int i = 1; i < size && curr->next != NULL; i++) {
                curr = curr->next;
            }
            struct ListNode* head2 = curr->next;
            curr->next = NULL;
            curr = head2;
            for (int i = 1; i < size && curr != NULL && curr->next != NULL; i++) {
                curr = curr->next;
            }
            struct ListNode* next = NULL;
            if (curr != NULL) {
                next = curr->next;
                curr->next = NULL;
            }
            pre->next = merge(head1, head2);
            while (pre->next != NULL) {
                pre = pre->next;
            }
            curr = next;
        }
    }
    return hair->next;
}
struct ListNode* sortList(struct ListNode* head) {
    return mergeSort(head);
}