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

    进阶：

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

    示例 1：
    image.png

    输入：head = [4,2,1,3]
    输出：[1,2,3,4]
    示例 2：
    image.png

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

    思路: 归并

    1. /**
    2.  * Definition for a singly-linked list.
    3.  * class ListNode {
    4.  *     public $val = 0;
    5.  *     public $next = null;
    6.  *     function __construct($val) { $this->val = $val; }
    7.  * }
    8.  */
    9. class Solution {
    11.     /**
    12.      * @param ListNode $head
    13.      * @return ListNode
    14.      */
    15.     function sortList($head){
    16.         if($head->next == null){
    17.             return $head;
    18.         }
    19.         $fast = $head->next;
    20.         $slow = $head;
    21.         while($fast !=null && $fast->next != null){
    22.             $fast = $fast->next->next;
    23.             $slow = $slow->next;
    24.         }
    26.         $tail = $slow->next;
    27.         $slow->next = null;
    29.         $head = $this->sortList($head);
    30.         $tail = $this->sortList($tail);
    31.         return $this->merge($head,$tail);
    32.     }
    34.     function merge($t1,$t2){
    35.         $node = new ListNode(-1);
    36.         $cur = $node;
    37.         while($t1 != null && $t2 !=null){
    38.             if($t1->val > $t2->val){
    39.                 $cur->next = $t2;
    40.                 $t2 = $t2->next;
    41.             }else{
    42.                 $cur->next = $t1;
    43.                 $t1 = $t1->next;
    44.             }
    45.             $cur = $cur->next;
    46.         }
    47.         $cur->next = ($t1 == null) ? $t2 : $t1;
    48.         return $node->next;
    49.     }
    50. }

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/sort-list
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。