首页 > 代码库 > Sort List
Sort List
Sort a linked list in O(n log n) time using constant space complexity.
分析:merge sort。
class Solution {public: ListNode *sortList(ListNode *head) { if(head == NULL || head->next == NULL) return head; int len = 0; for(ListNode * p = head; p; p = p->next) len++; return mergeSort(head, len); } ListNode * mergeSort(ListNode * head, int l){ if(l == 0) return NULL; if(l == 1) return head; int l_len = l/2; int r_len = l - l_len; ListNode * p = head; for(int i = 0; i < l_len -1; i++) p = p->next; ListNode * r_head = p->next; p->next = NULL; ListNode * l_list = mergeSort(head, l_len); ListNode * r_list = mergeSort(r_head, r_len); return merge(l_list, r_list); } ListNode * merge(ListNode * left, ListNode * right){ ListNode * dummy = new ListNode(-1); ListNode * p = dummy; while(left || right){ int lv = left?left->val:INT_MAX; int rv = right?right->val:INT_MAX; if(lv <= rv){ p->next = left; left = left->next; }else{ p->next = right; right = right->next; } p = p->next; } return dummy->next; }};
Sort List
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。