Sort a linked list in O(n log n) time using constant space complexity.
Example
Given 1->3->2->null, sort it to 1->2->3->null.
Challenge
Solve it by merge sort & quick sort separately.
LeetCode上的原题，请参见我之前的博客Sort List。
解法一：
class Solution { public: /** * @param head: The first node of linked list. * @return: You should return the head of the sorted linked list, using constant space complexity. */ ListNode *sortList(ListNode *head) { if (!head || !head->next) return head; ListNode *fast = head, *slow = head, *pre = head; while (fast && fast->next) { pre = slow; slow = slow->next; fast = fast->next->next; } pre->next = NULL; return merge(sortList(head), sortList(slow)); } ListNode *merge(ListNode *l1, ListNode *l2) { if (!l1) return l2; if (!l2) return l1; if (l1->val < l2->val) { l1->next = merge(l1->next, l2); return l1; } else { l2->next = merge(l1, l2->next); return l2; } } };
解法二：
class Solution { public: /** * @param head: The first node of linked list. * @return: You should return the head of the sorted linked list, using constant space complexity. */ ListNode *sortList(ListNode *head) { if (!head || !head->next) return head; ListNode *fast = head, *slow = head, *pre = head; while (fast && fast->next) { pre = slow; slow = slow->next; fast = fast->next->next; } pre->next = NULL; return merge(sortList(head), sortList(slow)); } ListNode *merge(ListNode *l1, ListNode *l2) { ListNode *dummy = new ListNode(-1); ListNode *cur = dummy; while (l1 && l2) { if (l1->val < l2->val) { cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } if (l1) cur->next = l1; if (l2) cur->next = l2; return dummy->next; } };
本文转自博客园Grandyang的博客，原文链接：链表排序[LintCode] Sort List ，如需转载请自行联系原博主。