[LeetCode]Sort List

题目描述：

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

解题方案：

题目要求的时间复杂度是 O(n log n)，常数级空间复杂度。所以这里用了归并排序，归并排序在数组上操作比较方便，但是这里要排序的是链表。我们用到两个指针将链表一份为二，一个指针q每次前进两步，一个指针p每次前进一步，当q到达链表结尾时，p到达链表中间位置。下面是该题的代码：

 1 class Solution {
 2 public:
 3     ListNode *sortList(ListNode *head) {
 4         return mergeSort(head);
 5     }
 6     ListNode *mergeSort(ListNode *head) {
 7         if (!head || head->next == NULL) {
 8             return head;
 9         }
10         ListNode *p = head;
11         ListNode *q = head;
12         ListNode *pre = NULL;
13         while (q && q->next != NULL) {
14             q = q->next->next;
15             pre = p;
16             p = p->next;
17         }
18         pre->next = NULL;
19         ListNode *llist = mergeSort(head);
20         ListNode *rlist = mergeSort(p);
21         return merge(llist, rlist);
22     }
23     ListNode *merge(ListNode *lhs, ListNode *rhs) {
24         ListNode *newhead = new ListNode(0);
25         ListNode *p = newhead;
26         while (lhs && rhs) {
27             if (lhs->val <= rhs->val) {
28                 p->next = lhs;
29                 lhs = lhs->next;
30             } else {
31                 p->next = rhs;
32                 rhs = rhs->next;
33             }
34             p = p->next;
35         }
36         if (lhs == NULL) {
37             p->next = rhs;
38         } else {
39             p->next = lhs;
40         }
41         p = newhead->next ;
42         newhead->next = NULL;
43         delete newhead;
44         return p;
45     }
46 };