给你链表的头结点 head
,请将其按 升序 排列并返回 排序后的链表 。
示例 1:
输入:head = [4,2,1,3] 输出:[1,2,3,4]
示例 2:
输入:head = [-1,5,3,4,0] 输出:[-1,0,3,4,5]
示例 3:
输入:head = [] 输出:[]
归并排序
思路
题目要求O(nlogn)时间复杂度和O(1)空间复杂度,使用归并排序而非是快速排序,归并排序比快排稳定。把链表分割成节点,再合并
代码
class Solution {
public:ListNode* merge(ListNode* list1, ListNode* list2){ListNode* mergelist = new ListNode(0); ListNode* node = mergelist;while(list1 != nullptr && list2 != nullptr){if(list1->val > list2->val){node->next = list2;list2 = list2->next;}else{node->next = list1;list1 = list1->next;}node = node->next;}if(list1 != nullptr)node->next = list1;else if(list2 != nullptr)node->next = list2;return mergelist->next;}ListNode* sortList(ListNode* head) { if(head == nullptr || head->next == nullptr)return head;int listlen = 0;ListNode* res = new ListNode(0, head);while(head != nullptr){head = head->next;++listlen;}for(int i=1; i<listlen; i*=2){ListNode* tmp = res->next;ListNode* tail = res;while(tmp != nullptr){ListNode* left = tmp;for(int j=1; j<i && tmp->next!=nullptr; ++j)tmp = tmp->next;ListNode* right = tmp->next;tmp->next = nullptr;tmp = right;for(int j=1; j<i && tmp!=nullptr && tmp->next!=nullptr; ++j)tmp = tmp->next;ListNode* next = nullptr;if(tmp != nullptr){next = tmp->next;tmp->next = nullptr;}tail->next = merge(left, right);while(tail->next != nullptr)tail = tail->next;tmp = next;}}ListNode* secondhead = res->next;delete res;return secondhead;}
};