[LeetCode] Sort List

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 <iostream>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<<tmp->val<<” “;tmp = tmp->next;}cout<<endl;}int main(){ListNode* head = new ListNode(-1);ListNode* node1 = new ListNode(8);head->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);}

大多数人想要改造这个世界，但却罕有人想改造自己。