45.Sort List（链表排序）
2020-12-13 03:35
标签：next head log link fast java output slow 思路 ??Medium Sort a linked list in O(n log n) time using constant space complexity. Example 1: Example 2: ??对链表进行归并排序，时间复杂为O(nlgn)，空间复杂度为O(1)。 45.Sort List（链表排序） 标签：next head log link fast java output slow 思路 原文地址：https://www.cnblogs.com/yjxyy/p/11080420.htmlLevel：
题目描述：
Input: 4->2->1->3
Output: 1->2->3->4Input: -1->5->3->4->0
Output: -1->0->3->4->5思路分析：
代码：
public class Solution{
public ListNode sortList(ListNode head){
if(head==null||head.next=null)
return head;
ListNode slow=head;
ListNode fast=head;
while(fast.next!=null&&fast.next.next!=null){
slow=slow.next;
fast=fast.next.next;
}
ListNode right=slow.next;
slow.next=null;//将左右链表断开
return merge(sortList(head),sortList(right));
}
public ListNode merge(ListNode head,ListNode right){
if(head==null)
return right;
if(right==null)
return head;
ListNode pHead=new ListNode(0);
if(head.val