Sort List

Sort a linked list in O(n log n) time using constant space complexity.

nlogn的排序有快速排序、归并排序、堆排序。双向链表用快排比较适合，堆排序也可以用于链表，单向链表适合用归并排序。以下是用归并排序的代码：

 1 /**
 2  * Definition for singly-linked list.
 3  * class ListNode {
 4  *     int val;
 5  *     ListNode next;
 6  *     ListNode(int x) {
 7  *         val = x;
 8  *         next = null;
 9  *     }
10  * }
11  */
12  
13  
14  /**
15  * Definition for singly-linked list.
16  * struct ListNode {
17  * int val;
18  * ListNode *next;
19  * ListNode(int x) : val(x), next(NULL) {}
20  * };
21  */
22 
23 public class Solution {
24     public ListNode sortList(ListNode head) {
25         if(head == null || head.next == null) return head;
26         ListNode fast = head, slow = head;
27         while(fast.next != null && fast.next.next != null){
28             fast = fast.next.next;
29             slow = slow.next;
30         }
31         fast = slow.next;
32         slow.next = null;
33         fast = sortList(fast);// 后半段
34         slow = sortList(head);//前半段
35         return merge(slow, fast);
36     }
37     ListNode merge(ListNode head1, ListNode head2){
38         if(head1 == null)return head2;
39         if(head2 == null)return head1;
40         ListNode ret = null, cur = null ;
41         if(head1.val < head2.val){
42             ret = head1; 
43             head1 = head1.next;
44         }else{
45             ret = head2;
46             head2 = head2.next;
47         }
48         cur = ret;
49         while(head1 != null && head2 != null){
50             if(head1.val < head2.val){
51                 cur.next = head1;
52                 head1 = head1.next;
53             }else{
54                 cur.next = head2;
55                 head2 = head2.next;
56             }
57             cur = cur.next;
58         }
59         if(head1 != null) cur.next = head1;
60         if(head2 != null) cur.next = head2;
61         return ret;
62     }
63 }

第二遍：

这次做的时候有一句话不一样。while(fast != null && fast.next != null) 在最开始分组时，结果导致runtime error。

Last executed input: {2,1}