给定一个节点数为n的无序单链表,对其按升序排序 时间复杂度 O(nlogn) 空间复杂度 O(n)
输入:
[1,3,2,4,5]
返回值:
{1,2,3,4,5}
归并
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
//合并两段有序链表 fast-template
ListNode* merge(ListNode* pHead1, ListNode* pHead2)
{
//一个已经为空了,直接返回另一个
if (pHead1 == NULL)
return pHead2;
if (pHead2 == NULL)
return pHead1;
//加一个表头
ListNode* head = new ListNode(0);
ListNode* cur = head;
//两个链表都要不为空
while (pHead1 && pHead2)
{
//取较小值的结点
if (pHead1->val <= pHead2->val)
{
cur->next = pHead1;
//只移动取值的指针
pHead1 = pHead1->next;
} else
{
cur->next = pHead2;
//只移动取值的指针
pHead2 = pHead2->next;
}
//指针后移
cur = cur->next;
}
//哪个链表还有剩,直接连在后面
if (pHead1)
cur->next = pHead1;
else
cur->next = pHead2;
//返回值去掉表头
return head->next;
}
ListNode* sortInList(ListNode* head)
{
//链表为空或者只有一个元素,直接就是有序的
if (head == NULL || head->next == NULL)
return head;
ListNode* left = head;
ListNode* mid = head->next;
ListNode* right = head->next->next; //快指针
//右边的指针到达末尾时,中间的指针指向该段链表的中间
while (right != NULL && right->next != NULL)
{
left = left->next;
mid = mid->next;
right = right->next->next;
}
//左边指针指向左段的左右一个节点,从这里断开
left->next = NULL;
//分成两段排序,合并排好序的两段
return merge(sortInList(head), sortInList(mid));
}
};
转换为数组排序
/**
* struct ListNode {
* int val;
* struct ListNode *next;
* ListNode(int x) : val(x), next(nullptr) {}
* };
*/
class Solution {
public:
ListNode* sortInList(ListNode* head)
{
vector<int> nums;
ListNode* p = head;
//遍历链表,将节点值加入数组
while(p != NULL)
{
nums.push_back(p->val);
p = p->next;
}
p = head;
//对数组元素排序
sort(nums.begin(), nums.end());
//遍历数组
for(int i = 0; i < nums.size(); i++)
{
//将数组元素依次加入链表
p->val = nums[i];
p = p->next;
}
return head;
}
};