网络异常,图片无法展示
|
给你链表的头结点 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)
时间复杂度和常数级空间复杂度下,对链表进行排序吗?
解题思路
归并排序
首先讲一下本题的最优解,同时也是官方题解。
将原链表拆分为每一个节点为链表的子链表。
然后将它们两两合并,合并过程中会对比两个节点的大小,小的在前,大的在后。
再将合并后的子链表两两进行合并,同样,合并过程中,比较两个链表节点的大小,小的在前,大的在后。
直到所有子链表合并为一个链表,就完成了输入链表的排序。
因为每一个链表节点是一个对象,所以在整个拆分过程中是不会增加额外的存储空间的。
同时也是因为链表这种数据结构不像数组,所以在拆分及合并过程中,会比较繁琐,这里我偷个懒就不去实现对应代码了,感兴趣的小伙伴可以去看一下官方题解。
暴力美学
接下来讲一下本题的另外一种我比较喜欢的解题思路。
首先遍历链表,将所有节点值存储到一个数组中。
然后对数组进行 sort
升序排序。
根据排序后的结果构建结果链表即可。
这样的一种解题方式,时间复杂度同样是 O(n log n)
的,但是因为我们开辟了一个数组存储节点值以及创建了新的结果链表,所以空间复杂度是 O(n)
的。
代码实现
var sortList = function(head) { // 特判输入链表为空,返回空 if(head === null) return null; // 初始化数组存储链表中的节点值 const arr = []; while(head){ arr.push(head.val); head = head.next; } // 对节点值数组升序排序 arr.sort((a,b) => a-b) // 根据排序数组构造结果链表 head = new ListNode(arr[0]) let cur = head; for(let i = 1;i<arr.length;i++){ cur.next = new ListNode(arr[i]) cur = cur.next; } // 返回结果链表 return head; }; 复制代码
至此我们就完成了 leetcode-148-排序链表
如有任何问题或建议,欢迎留言讨论!