148. 排序链表

题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

示例 1：

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 10⁴] 内
• -10⁵ <= Node.val <= 10⁵

进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

解题方法

• C 利用数组排序

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int my_cmp(int* a, int* b) { return *b - *a; }

struct ListNode* sortList(struct ListNode* head) {
    int val_tab[100000];
    struct ListNode* ptr = head;
    int val_size = 0;
    while (ptr) {
        val_tab[val_size] = ptr->val;
        val_size++;
        ptr = ptr->next;
    }

    qsort(val_tab, val_size, sizeof(int), my_cmp);
    ptr = head;
    while (val_size) {
        ptr->val = val_tab[val_size - 1];
        val_size--;
        ptr = ptr->next;
    }

    return head;
}