题解 | #单链表的排序#

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


void swap(int* a, int* b) {  
    int t = *a;  
    *a = *b;  
    *b = t;  
}  
  
int partition (int arr[], int low, int high) {  
    int pivot = arr[high];    // pivot  
    int i = (low - 1);  // Index of smaller element  
  
    for (int j = low; j <= high- 1; j++) {  
        // If current element is smaller than or equal to pivot  
        if (arr[j] <= pivot) {  
            i++;    // increment index of smaller element  
            swap(&arr[i], &arr[j]);  
        }  
    }  
    swap(&arr[i + 1], &arr[high]);  
    return (i + 1);  
}  
  
void quickSort(int arr[], int low, int high) {  
    if (low < high) {  
        /* pi is partitioning index, arr[p] is now at right place */  
        int pi = partition(arr, low, high);  
  
        // Separately sort elements before partition and after partition  
        quickSort(arr, low, pi - 1);  
        quickSort(arr, pi + 1, high);  
    }  
}  
  
void printArray(int arr[], int size) {  
    int i;  
    for (i=0; i < size; i++)  
        printf("%d ", arr[i]);  
    printf("\n");  
}

struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    struct ListNode* p = head;
    int count = 0;
    while(p){
        count++;
        p=p->next;
    }
    p = head;
    int arr[count];
    int num = 0;
    while(p){
        arr[num] = p->val;
        num++;
        p = p->next;
    }
    num = 0;
    p = head;
    quickSort(arr, 0, count-1);
    while(p){
        p->val = arr[num];
        p = p->next;
        num++;
    }
    return head;
    
}

将链表中的值取出保存在一个数组中，再使用快排进行排序，最后将排序好的数组依次给链表赋值。