题解 | 单链表的排序

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

int cmp(const void *a, const void *b) {
    return (*(int*)a - *(int*)b);
}

#include <stdlib.h>
struct ListNode* sortInList(struct ListNode* head ) {
    // write code here
    struct ListNode *p = NULL;
    int len = 0;
    p = head;
    while(p != NULL)
    {
        p = p->next;
        len++;
    }
    
    
    int *arr = (int*)malloc(sizeof(int) * len );
    p = head;
    int count = 0;
    while(p)
    {
        arr[count++] = p->val;
        p = p->next;
    }

    qsort(arr, count, sizeof(int),cmp);

    p = head;
    int i = 0; 
    while(p)
    {
        p->val = arr[i++];
        p = p->next;
    }
    
    free(arr);

    return head;
}

思路：

1.遍历链表，得出链表长度。

2.利用该长度，动态分配数组。将链表中的值存入数组中。

3.利用C库的qsort函数给数组排序。

4.之后再将数组的值赋给链表