2019-09-16 吴亲库里 库里的深夜食堂
这道题从案例中你应该看出来要我们干嘛了，只是要求在O(nlogn)时间复杂度和恒定的空间复杂度中完成
时间复杂度限制下，符合要求的常规排序算法可以用快速，归并.....来完成，这里使用的是归并排序，归并排序最重要的的就是合并操作了，而且他合并的是两个有序集，对于当前的链表来说，只有当链表只有一个结点的时候，此链表才是有序链表。不断的拆分链表，这是递，当拆分的两个链表都只剩下一个结点时，merge，然后回到上一层继续合并，这是归。所以每一次回来合并的都是有序链表。
/**
* Definition for a singly-linked list.
* class ListNode {
* public $val = 0;
* public $next = null;
* function __construct($val) { $this->val = $val; }
* }
*/
class Solution {
/**
* @param ListNode $head
* @return ListNode
*/
function sortList($head) {
if(!$head || !$head->next) return $head;
$slow=$fast=$head;
while($fast && $fast->next){
$pre=$slow;
$fast=$fast->next->next;
$slow=$slow->next;
}
$pre->next=null;
return $this->merge($this->sortlist($head),$this->sortlist($slow));
}
function merge($l1,$l2){
$node=new ListNode(-1); //随意塞入一个数字作为新链表头，最后取next即可。
$cur=$node;
while($l1 && $l2){
if($l1->val>$l2->val){
$cur->next=$l2;
$l2=$l2->next;
}else{
$cur->next=$l1;
$l1=$l1->next;
}
$cur=$cur->next;
}
if($l1){
$cur->next=$l1;
}
if($l2){
$cur->next=$l2;
}
return $node->next;
}
}
