TOP101题解 | BM12#单链表的排序#

#include<stdlib.h>
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * @author Senky
 * @date 2023.04.23
 * @par url https://www.nowcoder.com/creation/manager/content/584337070?type=column&status=-1
 * @brief 时间复杂度是O(nlogn),用快排
 * @param head ListNode类 the head node
 * @return ListNode类
 */
 int compar_t(const void* p1, const void* p2)
 {
    return (*(int *)p1)-
        (*(int *)p2);
 }
struct ListNode* sortInList(struct ListNode* head ) 
{
    // write code here
    int size = 0;
    int str_index = 0;

    struct ListNode* p = head;

    /*计算链表的长度*/
    while(p)
    {
        size++;
        p = p->next;
    }

    /*申请数组*/
    int* str = malloc(size*sizeof(int));

    /*记录链表数据域*/
    {
        p = head;
        while(p)
        {
            str[str_index++] = p->val;
            p = p->next;
        }
    }

    /*排序数组*/
    qsort(str,size,sizeof(str[0]), compar_t);

    /*将排序好的证书元素写回链表*/
    {
        p = head;
        str_index = 0;
        while(p)
        {
            p->val = str[str_index++];
            p = p->next;
        }
    }

    return head;
}