在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
区块链毕设网qklbishe.com为您提供问题的解答
在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
/** * struct ListNode { * int val; * struct ListNode *next; * }; */ #include <endian.h> class Solution { public: /** * * @param head ListNode类 * @return ListNode类 */ ListNode* SortList(ListNode* head) { // write code here return sortList(head, nullptr); } ListNode* sortList(ListNode* head, ListNode* tail) { if(head == nullptr) return head; if(head->next == tail) { head->next = nullptr; return head; } ListNode* slow = head, *fast = head; while(fast != tail) { slow = slow->next; fast = fast->next; if(fast != tail) { fast = fast->next; } } ListNode* mid = slow; return merge(sortList(head, mid), sortList(mid, tail)); } ListNode* merge(ListNode* head1, ListNode* head2) { ListNode* dummyHead = new ListNode(0); ListNode* tmp = dummyHead; ListNode* tmp1 = head1, *tmp2 = head2; while(tmp1 != nullptr && tmp2 != nullptr) { if(tmp1->val < tmp2->val) { tmp->next = tmp1; tmp1 = tmp1->next; } else { tmp->next = tmp2; tmp2 = tmp2->next; } tmp = tmp->next; } if(tmp1 != nullptr) tmp->next = tmp1; else if(tmp2 != nullptr) tmp->next = tmp2; return dummyHead->next; } };
42:48
以上就是关于问题在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。的答案
欢迎关注区块链毕设网-
web3一级市场套利打新赚钱空投教程
区块链NFT链游项目方科学家脚本开发培训
.jpg){kind=link}