题解 | #单链表的排序#

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param head ListNode类 the head node
 * @return ListNode类
 */
void swap(int* a, int* b) {
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}

void quickSort(int* arr, int begin, int end) {
    if (begin >= end || arr == NULL)
        return;
    int left = begin;
    int right = end;
    int key = begin;
    while (begin < end) {
        /* 右边选小, 等号防止和 key 值相等, 防止顺序 begin 和 end 越界 */
        while (arr[end] >= arr[key] && begin < end)
            --end;
        /* 左边选大 */
        while (arr[begin] <= arr[key] && begin < end)
            ++begin;
        swap(&arr[begin], &arr[end]);
    }
    swap(&arr[key], &arr[end]);
    key = end;
    quickSort(arr, left, key - 1);
    quickSort(arr, key + 1, right);
}

struct ListNode* sortInList(struct ListNode* head) {
    // write code here
    if (head == NULL || head->next == NULL)
        return head;
    int len = 0;
    struct ListNode* dummy = head;
    while (dummy != NULL) {
        len++;
        dummy = dummy->next;
    }
    int* arr = (int*)malloc(sizeof(int) * len);
    dummy = head;
    int i = 0;
    // 链表转数组
    while (dummy != NULL) {
        arr[i++] = dummy->val;
        dummy = dummy->next;
        //i++;
    }
    quickSort(arr, 0, len - 1);
    dummy = head;
    i = 0;
    // 数组重新转链表
    while (dummy != NULL) {
        dummy->val = arr[i++];
        dummy = dummy->next;
        //i++;
    }
    return head;
}