首页 > 代码库 > leetcode. Sort List
leetcode. Sort List
Sort a linked list in O(n log n) time using constant space complexity.
时间复杂度为O(nlbn)的排序一般选择归并排序或快速排序，而且链表的归并不需要重新分配空间，也只需要常量的空间。
一下是链表的归并排序实现：
1 ListNode *sortList(ListNode *head) 2 { 3 head = merge_sort(head); 4 return head; 5 } 6 7 ListNode *merge_sort(ListNode *head) 8 { 9 if (head == NULL || head->next == NULL)10 return head;11 ListNode *fast = head, *slow = head, *left = head, *right;12 while (fast != NULL && fast->next != NULL)13 {14 fast = fast->next->next;15 if (fast == NULL)16 break;17 slow = slow->next;18 }19 right = slow->next;20 slow->next = NULL;21 22 left = merge_sort(left);23 right = merge_sort(right);24 head = merge(left, right);25 return head;26 }27 28 ListNode *merge(ListNode *l1, ListNode *l2) 29 {30 ListNode *dummy1 = new ListNode(INT_MIN), *dummy2 = new ListNode(INT_MIN), *p, *r;31 dummy1->next = l1;32 dummy2->next = l2;33 34 p = dummy1;35 while (p->next != NULL && dummy2->next != NULL)36 {37 if (p->next->val > dummy2->next->val)38 {39 r = dummy2->next;40 dummy2->next = r->next;41 r->next = p->next;42 p->next = r;43 }44 p = p->next;45 }46 47 if (dummy2->next != NULL)48 {49 p->next = dummy2->next;50 dummy2->next = NULL;51 }52 53 p = dummy1->next;54 delete dummy1;55 delete dummy2;56 return p;57 }
leetcode. Sort List
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。