【力扣】148. 排序链表

简介: 【力扣】148. 排序链表

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 * 104] 内
  • -105 <= Node.val <= 105

进阶:你可以在 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;
}



相关文章
|
11月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
122 1
|
11月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
147 0
Leetcode第21题(合并两个有序链表)
|
5月前
|
算法 Go
【LeetCode 热题100】23:合并 K 个升序链表(详细解析)(Go语言版)
本文详细解析了 LeetCode 热题 23——合并 K 个升序链表的两种解法:优先队列(最小堆)和分治合并。题目要求将多个已排序链表合并为一个升序链表。最小堆方法通过维护节点优先级快速选择最小值,;分治合并则采用归并思想两两合并链表。文章提供了 Go 语言实现代码,并对比分析两种方法的适用场景,帮助读者深入理解链表操作与算法设计。
178 10
|
11月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
80 4
|
11月前
|
算法
【链表】算法题(二) ----- 力扣/牛客
【链表】算法题(二) ----- 力扣/牛客
|
11月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
92 0
Leetcode第三十三题(搜索旋转排序数组)
|
11月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
120 0
LeetCode第二十四题(两两交换链表中的节点)
|
11月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
118 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
11月前
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
(剑指offer)18、删除链表的节点—22、链表中倒数第K个节点—25、合并两个排序的链表—52、两个链表的第一个公共节点(2021.12.07)
124 0
|
11月前
|
算法
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
❤️算法笔记❤️-(每日一刷-83、删除排序链表中的重复项)
118 0