题目:
难度:Middle
相关话题:排序
、链表
在O (n logn ) 时间复杂度和常数级空间复杂度下,对链表进行排序。
示例 1:
输入: 4->2->1->3
输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0
输出: -1->0->3->4->5
思路:
这里使用了归并排序
,分为分割和合并两个部分。
/**
* @来源: Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* @介绍:一个致力于帮助开发者用代码改变世界为使命的平台,每天都可以在这里找到技术世界的头条内容
* Definition for singly-linked list.
* function ListNode(val) {
* this.val = val;
* this.next = null;
* }
*/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var sortList = function(head) {
return divid(head)
function divid(node){
if(!node || !node.next)return node
let fast=node,slow=node,prev
while(fast && fast.next){
prev=slow
slow=slow.next
fast=fast.next.next
}
prev.next=null
return merge(divid(node),divid(slow))
}
function merge(l1,l2){
if(!l1)return l2
else if(!l2)return l1
else if(l1.val<l2.val){
l1.next=merge(l1.next,l2)
return l1
}else{
l2.next=merge(l1,l2.next)
return l2
}
}
};
扩展阅读: