Leetcode 148.排序链表

排序链表

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

示例 1:

输入: 4->2->1->3

输出: 1->2->3->4

示例 2:

输入: -1->5->3->4->0

输出: -1->0->3->4->5

 1 class Solution {
 2     public ListNode sortList(ListNode head) {
 3         if(head==null||head.next==null) return head;
 4         return mergeSort(head);
 5     }
 6 
 7     private ListNode mergeSort(ListNode head){
 8         if(head==null||head.next==null) return head;
 9         //分治
10         ListNode p1=head;
11         ListNode p2=head;
12         while(p2.next!=null&&p2.next.next!=null){
13             p1=p1.next;
14             p2=p2.next.next;
15         }
16         ListNode left=head;
17         ListNode right=p1.next;
18         p1.next=null;
19         //排序子链表
20         left=mergeSort(left);
21         right=mergeSort(right);
22         //合并
23         if(left==null) return right;
24         if(right==null) return left;
25         ListNode h=new ListNode(-1);
26         ListNode p=h;
27         while(left!=null && right!=null){
28             if(left.val<right.val){
29                 p.next=left;
30                 left=left.next;
31                 p=p.next;
32             }else{
33                 p.next=right;
34                 right=right.next;
35                 p=p.next;
36             }
37         }
38         if(left==null) p.next=right;
39         else p.next=left;
40         return h.next;
41     }
42 }