Sort List
Sort a linked list in O(n log n) time using constant space complexity.
要求时间复杂度为O(nlogn)，那么不能用quickSort了（最坏O(n^2)），所以使用mergeSort.
通常写排序算法都是基于数组的，这题要求基于链表。所以需要自己设计函数获得middle元素，从而进行切分。
参考Linked List Cycle II中的“龟兔赛跑”思想：兔子前进两步，龟前进一步，从而可以获得middle元素。
class Solution { public: ListNode *getMiddle(ListNode *head) { ListNode *fast = head; ListNode *slow = head; while(true) { if(fast->next != NULL) { fast = fast->next; if(fast->next != NULL) fast = fast->next; else break; slow = slow->next; } else break; } return slow; } ListNode *merge(ListNode *list1, ListNode *list2) {// merge sorted list ListNode *newhead = new ListNode(0); ListNode *head = newhead; while(list1 != NULL && list2 != NULL) { if(list1->val < list2->val) { newhead->next = list1; list1 = list1->next; } else { newhead->next = list2; list2 = list2->next; } newhead = newhead->next; } if(list1 == NULL) newhead->next = list2; else newhead->next = list1; return head->next; } ListNode *sortList(ListNode *head) { if(head == NULL || head->next == NULL) return head; ListNode *mid = getMiddle(head); ListNode *head2 = mid->next; mid->next = NULL; //attention! return merge(sortList(head), sortList(head2)); } };
【LeetCode】Sort List,布布扣,bubuko.com
原文：http://www.cnblogs.com/ganganloveu/p/3763707.html