C++刷LeetCode（148. 排序链表）【归并排序】

糖逗

题目描述：

1. 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
   
2. 
   
3. 示例 1:
   
4. 
   
5. 输入: 4->2->1->3
   
6. 输出: 1->2->3->4
   
7. 示例 2:
   
8. 
   
9. 输入: -1->5->3->4->0
   
10. 输出: -1->0->3->4->5
    
11. 
    
12. 来源：力扣（LeetCode）
    
13. 链接：https://leetcode-cn.com/problems/sort-list
    
14. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

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* merge(ListNode* head1, ListNode* head2){//递归
    
12.         if(head1 == NULL)return head2;
    
13.         if(head2 == NULL)return head1;
    
14.         if(head1 -> val < head2 -> val){
    
15.             head1 -> next = merge(head1 -> next, head2);
    
16.             return head1;
    
17.         }else{
    
18.             head2 -> next = merge(head1, head2 -> next);
    
19.             return head2;
    
20.         }
    
21.     }
    
22.     ListNode* sortList(ListNode* head) {//递归
    
23.         if(head == NULL || head -> next == NULL)return head;
    
24.         ListNode* pre = head, *slow = head, *fast = head;
    
25.         while(fast && fast -> next){
    
26.             pre = slow;
    
27.             slow = slow -> next;
    
28.             fast = fast -> next -> next;
    
29.         }//这样切出的slow会多出一个，因此要用pre
    
30.         pre -> next = NULL;
    
31.         return merge(sortList(head), sortList(slow));
    
32.     }
    
33. };

复制代码

参考链接：https://leetcode-cn.com/problems ... ian-biao-by-lioney/