LeetCode148 Sort List

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

分析：

因为题目要求复杂度为O(nlogn),故可以考虑归并排序的思想。

归并排序的一般步骤为：

1）将待排序数组（链表）取中点并一分为二；

2）递归地对左半部分进行归并排序；

3）递归地对右半部分进行归并排序；

4）将两个半部分进行合并（merge）,得到结果。

所以对应此题目，可以划分为三个小问题：

1）找到链表中点（快慢指针思路，快指针一次走两步，慢指针一次走一步，快指针在链表末尾时，慢指针恰好在链表中点）；

2）写出merge函数，即如何合并链表。（可以参见merge-two-sorted-lists 一题）

3）写出mergesort函数，实现上述步骤。

代码：

 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* findMiddle(ListNode* head){
12         ListNode* chaser = head;
13         ListNode* runner = head->next;
14         while(runner != NULL && runner->next != NULL){
15             chaser = chaser->next;
16             runner = runner->next->next;
17         }
18         return chaser;
19     }
20      
21  ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
22         if(l1 == NULL){
23             return l2;
24         }
25         if(l2 == NULL){
26             return l1;
27         }
28         ListNode* dummy = new ListNode(0);
29         ListNode* head = dummy;
30         while(l1 != NULL && l2 != NULL){
31             if(l1->val > l2->val){
32                 head->next = l2;
33                 l2 = l2->next;
34             }
35             else{
36                 head->next = l1;
37                 l1 = l1->next;
38             }
39             head = head->next;
40         }
41         if(l1 == NULL){
42             head ->next = l2;
43         }
44         if(l2 == NULL){
45             head->next = l1;
46         }
47         return dummy->next;
48     }
49      
50     ListNode* sortList(ListNode* head) {
51         if(head == NULL || head ->next == NULL){
52             return head;
53         }
54         ListNode* middle = findMiddle(head);
55         ListNode* right = sortList(middle->next);
56         middle -> next = NULL;
57         ListNode* left = sortList(head);
58         return mergeTwoLists(left, right);
59     }
60 };