Sort a linked list in O(n log n) time using constant space complexity.
解题思路
可以利用归并排序解决该问题。普通的归并排序算法时间复杂度为O(nlogn)，空间复杂度为O(n)，因为需要建立两个数组来存储原来数组的值，这两个数组的长度加起来恰好为原数组的长度。但是对于链表可以省去复制两个已经排好序的数组的操作，从而使空间复杂度达到O(1)。实现代码
/***************************************************************** * @Author : 楚兴 * @Date : 2015/2/16 21:46 * @Status : Accepted * @Runtime : 79 ms******************************************************************/#include using namespace std;struct ListNode { int val; ListNode *next; ListNode(int x) : val(x), next(NULL) {}};class Solution {public: ListNode * getMiddleOfList(ListNode *head) { ListNode *p = head; ListNode *q = head; while(q->next != NULL && q->next->next != NULL) { p = p->next; q = q->next->next; } return p; } ListNode *mergeList(ListNode *head1, ListNode *head2) { ListNode *merge = new ListNode(-1); ListNode *tmp = merge; while(head1 != NULL && head2 != NULL) { if (head1->val <= head2->val) { tmp->next = head1; head1 = head1->next; } else { tmp->next = head2; head2 = head2->next; } tmp = tmp->next; } if(head1 == NULL) { tmp->next = head2; } else { tmp->next = head1; } return merge->next; } ListNode *sortList(ListNode *head) { if (head == NULL || head->next == NULL) { return head; } ListNode *middle = getMiddleOfList(head); ListNode *next = middle->next; middle->next = NULL; return mergeList(sortList(head), sortList(next)); }};void print(ListNode *head){ ListNode *tmp = head; while(tmp) { cout< val<<" "; tmp = tmp->next; } cout< next = node1; ListNode* node2 = new ListNode(5); node1->next = node2; ListNode* node3 = new ListNode(9); node2->next = node3; ListNode* node4 = new ListNode(0); node3->next = node4; ListNode* node5 = new ListNode(1); node4->next = node5; ListNode* node6 = new ListNode(3); node5->next = node6; ListNode* node7= new ListNode(6); node6->next = node7; ListNode* node8 = new ListNode(4); node7->next = node8; print(head); Solution s; s.sortList(head); print(head);}