首页 > 代码库 > [LintCode] Sort List 链表排序
[LintCode] Sort List 链表排序
Sort a linked list in O(n log n) time using constant space complexity.
Have you met this question in a real interview?
Yes
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; }};
[LintCode] Sort List 链表排序
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。