Sort a linked list in
O(
n log
n) time using constant space complexity.
[Thoughts]
O(nlgn)的排序算法没几个，无非就是quick sort， heap sort和merge sort. 对于链表排序来说，难点之一就是如何O(1)定位节点。如果是数组，那么可以通过下标直接找到节点，但是对于链表，很明显没有下标这个东西可以用，如果需要定位到第k个元素，只能从节点头部顺序的访问K次，但是，如果排序中每一个定位操作都要这样做的话，就太慢了。
所以，问题其实就是，如何能够节省链表节点的定位时间。如果采用merge sort的话，就可以通过递归的特性来避免这个时间损耗。具体看代码
[Code]
关键的部分已用红字标明。通过递归调用的顺序来保证节点的访问顺序。
1: ListNode *sortList(ListNode *head) {
2: if(head == NULL) return NULL;
3: int len = 0;
4: ListNode* it = head;
5: while(it!= NULL)
6: {
7: len++;
8: it = it->next;
9: }
10: ListNode* newHead = Sort(&head, len);
11: return newHead;
12: }
13: ListNode* Sort(ListNode** head, int length)
14: {
15: if (length == 1)
16: {
17: ListNode* temp = *head;
18: *head = (*head)->next; // 确保head每被访问一次，则向后移动一次
19: temp->next = NULL; // 尾节点需要为NULL，否则Merge函数没法使用
20: return temp;
21: }
22: ListNode* leftHead = Sort(head, length / 2);
23: ListNode* rightHead = Sort(head, length - length / 2);
24: ListNode* newHead = Merge(leftHead, rightHead);
25: return newHead;
26: }
27: ListNode* Merge(ListNode* first, ListNode* second) // 普通的链表merge函数
28: {
29: ListNode* head = new ListNode(-1);
30: ListNode* cur = head;
31: while(first!=NULL || second!=NULL)
32: {
33: int fv = first == NULL? INT_MAX:first->val;
34: int sv = second == NULL? INT_MAX:second->val;
35: if(fv<=sv)
36: {
37: cur->next = first;
38: first = first->next;
39: }
40: else
41: {
42: cur->next = second;
43: second = second->next;
44: }
45: cur = cur->next;
46: }
47: cur = head->next;
48: delete head;
49: return cur;
50: }
Update 08/23/2014
True. Recursion is not constant space. I didn't read the problem description carefully. Here, add an implementation via iteration.
Same idea as merge sort. One example as below:
For each round, the iteration is O(n). And for merge sort, we totally need run the iteration for lg(n) round(the height of recursion tree). So, the total time complexity is O(nlgn). Maybe someone can share a brief implementation. My current code is a bit fat.
1: ListNode *sortList(ListNode *head) {
2: // Get length first
3: ListNode* p = head;
4: int len = 0;
5: while (p != NULL)
6: {
7: p = p->next;
8: len++;
9: }
10: ListNode* fakehead = new ListNode(-1);
11: fakehead->next = head;
12: for (int interval = 1; interval <= len; interval = interval * 2)
13: {
14: ListNode* pre = fakehead;
15: ListNode* slow = fakehead->next, *fast = fakehead->next;
16: while (fast != NULL || slow != NULL)
17: {
18: int i = 0;
19: while (i< interval && fast != NULL)
20: {
21: fast = fast->next; //move fast pointer ahead 'interval' steps
22: i++;
23: }
24: //merge two lists, each has 'interval' length
25: int fvisit = 0, svisit = 0;
26: while (fvisit < interval && svisit<interval && fast != NULL && slow != NULL)
27: {
28: if (fast->val < slow->val)
29: {
30: pre->next = fast;
31: pre = fast;
32: fast = fast->next;
33: fvisit++;
34: }
35: else
36: {
37: pre->next = slow;
38: pre = slow;
39: slow = slow->next;
40: svisit++;
41: }
42: }
43: while (fvisit < interval && fast != NULL)
44: {
45: pre->next = fast;
46: pre = fast;
47: fast = fast->next;
48: fvisit++;
49: }
50: while (svisit < interval && slow != NULL)
51: {
52: pre->next = slow;
53: pre = slow;
54: slow = slow->next;
55: svisit++;
56: }
57: pre->next = fast;
58: slow = fast;
59: }
60: }
61: ListNode* newhead = fakehead->next;
62: delete fakehead;
63: return newhead;
64: }
