LeetCode OJ：Sort List（排序链表）

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

题目要求在常数控件内以O(nlogn)的事件复杂度来排序链表。

常数空间内我没有实现，O(nlogn)的话使用归并排序就可以了吗，下面是代码：

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* sortList(ListNode* head) {
12         if(!head || !head->next)
13             return head;
14         return mergeSort(head);
15     }
16 
17     ListNode * mergeSort(ListNode * head)
18     {
19         if(head == NULL || head->next == NULL) return head;
20         ListNode * fastP = head;
21         ListNode * slowP = head;
22         ListNode * slowPre = slowP; //这里生成快慢指针的时候应该注意一点，选一个pre节点，否则直接用slowP的话那么分成的两段是不平衡的
23         for(; fastP != NULL && fastP->next != NULL; fastP = fastP->next->next, slowP = slowP->next){
24             slowPre = slowP;
25         }
26         ListNode * head1 = head;
27         ListNode * head2 = slowP;
28         slowPre->next = NULL;//截断list
29         head1 = mergeSort(head1);
30         head2 = mergeSort(head2);
31         return merge(head1, head2);
32     }
33 
34     ListNode * merge(ListNode * head1, ListNode * head2)
35     {
36         ListNode * ret = new ListNode(0);   //记录首节点的位置
37         ListNode * helper = ret;    //这里应该注意，helper是用来标记下一个插入位置用的。
38         while(head1 && head2){
39             if(head1->val < head2->val){
40                 helper->next = head1;
41                 head1 = head1->next;
42             }else{
43                 helper->next = head2;
44                 head2 = head2->next;
45             }
46             helper = helper->next;//指向当前链表的尾节点
47         }
48         if(head1 == NULL)
49                 helper->next = head2;
50              else 
51                 helper->next = head1;
52         helper = ret->next;
53         ret->next = NULL;  //销毁helper节点
54         delete ret;
55         return helper;
56     }
57 
58 };

下面的事java版，写了很多的局部变量，主要事图个方便啊，方法与上相同，可以满足题目的限制条件。代码如下所示：

 1 public class Solution {
 2     public ListNode sortList(ListNode head) {
 3         if(head == null || head.next == null)
 4             return head;
 5         return mergeSort(head);
 6     }
 7 
 8     public ListNode mergeSort(ListNode head){
 9         if(head == null || head.next == null) return head;
10         ListNode fast = head;
11         ListNode slow = head;
12         ListNode slowPre = new ListNode(-1);
13         slowPre.next = head;
14         while(fast != null){
15             fast = fast.next;
16             slow = slow.next;
17             slowPre = slowPre.next;
18             if(fast != null)
19                 fast = fast.next;
20         }
21         ListNode list1 = head;
22         ListNode list2 = slow;
23         slowPre.next = null;
24         list1 = mergeSort(list1);
25         list2 = mergeSort(list2);
26         return merge(list1, list2);
27     }
28     
29     public ListNode merge(ListNode head1, ListNode head2){
30         if(head1 == null) return head2;
31         if(head2 == null) return head1;
32         ListNode helperP = new ListNode(-1);
33         helperP.next = head1;
34         ListNode pPre = helperP;
35         ListNode p = head1;
36         ListNode helperQ = new ListNode(-1);
37         helperQ.next = head2;
38         ListNode qPre = helperQ;
39         ListNode q = head2;
40         while(p != null && q != null){
41             if(p.val < q.val){
42                 p=p.next;
43                 pPre = pPre.next;
44             }else{
45                 pPre.next = q;
46                 qPre.next = q.next;
47                 q.next = p;
48                 q = qPre.next;
49                 pPre = pPre.next;
50             }
51         }
52         if(p == null){
53             pPre.next = helperQ.next;
54             helperQ.next = null;
55         }
56         return helperP.next;
57     }
58 }