sort-list 归并排序链表

题目：

在O(n log n)的时间内使用常数级空间复杂度对链表进行排序。

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

示例;

输入：{3,2,4}　　　　输出：{2,3,4}

代码：

 1 /**
 2  * struct ListNode {
 3  *    int val;
 4  *    struct ListNode *next;
 5  * };
 6  */
 7 
 8 class Solution {
 9 public:
10     /**
11      * 
12      * @param head ListNode类 
13      * @return ListNode类
14      */
15     ListNode* FindMiddleNode(ListNode* head) {
16         ListNode* fast = head; //利用快慢指针找到当前中间节点
17         ListNode* slow = head;
18         while(fast->next != NULL && fast->next->next != NULL){
19             fast = fast->next->next;
20             slow = slow->next;
21         }
22         return slow;
23     }
24     ListNode* MergeList(ListNode* l1, ListNode* l2) {
25         if(l1 == NULL)
26             return l2;
27         if(l2 == NULL)
28             return l1;
29         ListNode* result; //结果
30         ListNode* newhead; //头节点
31         auto first = l1->next; //表示归并排序中的两个分区
32         auto second = l2->next;
33         if(l1->val > l2->val){ //l1较小则为头节点，反之则头节点为l2
34             result = newhead = l2;
35             first = l1;
36         }
37         else{
38             result = newhead = l1;
39             second = l2;
40         }
41         while(first != NULL || second != NULL){
42             if(second == NULL){ //当第二块为空
43                 result->next = first; break;
44             }
45             else if(first == NULL){ //当第一块为空
46                 result->next = second; break;
47             }
48             // 归并排序，较小的先插入result的尾部，由于这里在sort函数中有将右末尾结点设为NULL所以会停止循环
49             if(first->val > second->val){
50                 result->next = second;
51                 second = second->next;
52                 result = result->next;
53             }
54             else{
55                 result->next = first;
56                 first = first->next;
57                 result = result->next;
58             }
59         }
60         return newhead;
61     }
62     ListNode* sortList(ListNode* head) {
63         if(head == NULL || head->next == NULL)
64             return head;
65         ListNode* mid = FindMiddleNode(head);
66         ListNode* midnext = mid->next;
67         mid->next = NULL; //将链表划分
68         return MergeList(sortList(head), sortList(midnext));
69     }
70 };

我的笔记：

由于本函数的要求时间复杂度为O(nlogn)，故使用归并排序法。

leetcode官网详解：https://leetcode-cn.com/problems/sort-list/solution/148-pai-xu-lian-biao-bottom-to-up-o1-kong-jian-by-