Leetcode | Sort List

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

merge sort、heap sort和quick sort都是O(nlgn)，但是mergesort和quicksort都是递归的，不是constant space的，heapsort需要有随机访问才行。

mergesort的bottom up实现是可以常数空间的。也适用于链表。

如果是数组，还可以用heapsort。

 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     // merge two list, and return last element (not NULL)
12     ListNode* merge(ListNode *nh, ListNode *p1, ListNode *p2) {
13         while (p1 || p2) {
14             if (p1 && (p2 == NULL || p1->val < p2->val)) {
15                 nh->next = p1;
16                 p1 = p1->next;
17             } else {
18                 nh->next = p2;
19                 p2 = p2->next;
20             }
21             nh = nh->next;
22         }
23         return nh;
24     }
25     
26     // get length of list
27     int getLength(ListNode *head) {
28         int n = 0;
29         while (head) {
30             n++;
31             head = head->next;
32         }
33         return n;
34     }
35     
36     ListNode *sortList(ListNode *head) {
37         int n = getLength(head);
38         ListNode *p1, *p2, *tmp, *newH1, *tail;
39         
40         // merge sort, bottom up
41         for (int l = 1; l < n; l *= 2) {
42             p1 = head;
43             tail = head = NULL; // head of the whole list
44             while (p1) {
45                 p2 = p1;
46                 for (int i = 1; i < l && p2; ++i) {
47                     p2 = p2->next;
48                 }
49                 if (!p2) break;
50                 tmp = p2->next;
51                 p2->next = NULL; // set tail of list 1 to NULL
52                 p2 = tmp; 
53                 for (int i = 1; i < l && tmp; ++i) {
54                     tmp = tmp->next;
55                 }
56                 if (tmp) {
57                     newH1 = tmp->next; // get next head of list 1
58                     tmp->next = NULL; // set tail of list 2 to NULL
59                 } else {
60                     newH1 = NULL;
61                 }
62                 ListNode h(0);
63                 ListNode *last = merge(&h, p1, p2);
64                 if (tail) tail->next = h.next; // connect the sorted part with the current two list
65                 if (!head) head = h.next;
66                 tail = last;
67                 last->next = newH1;
68                 p1 = newH1;
69             }
70         }
71         return head;
72     }
73 };