少年的书桌上没有虚度的光阴
题目描述
请你对链表进行排序
思路分析
-
核心思想：归并排序
有三个部分
链表排序实现
1. merge 函数
21.见 合并两个有序链表，
-
首先创建一个虚拟头节点
newhead，并使用指针tail来构建合并后的链表。 -
通过循环比较
list1和list2节点的值，将较小值的节点连接到tail后面，并相应地移动指针。 -
当其中一个链表遍历完后，将另一个链表的剩余部分直接连接到
tail后面。 -
最后返回虚拟头节点的下一个节点，即合并后链表的头节点。
2. findMiddle 函数
该函数用于寻找链表的中间节点，采用快慢指针的方法：
-
fast指针每次移动两步，slow指针每次移动一步。 -
当
fast指针到达链表末尾时，slow指针就指向链表的中间节点。
3. sortList 函数
这是核心的排序函数，使用归并排序算法对链表进行排序：
-
首先判断链表是否为空或只有一个节点，如果是则直接返回该链表。
-
调用
findMiddle函数找到链表的中间节点，将链表分成左右两部分。 -
递归地对左右两部分链表分别调用
sortList函数进行排序。 -
最后调用
merge函数将两个有序的子链表合并成一个有序链表。
完整代码
class Solution {
public:
// 合并两个有序链表
ListNode* merge(ListNode* list1, ListNode* list2) {
auto newhead = new ListNode(0); // 使用明确的类型名称
auto tail = newhead;
while (list1 && list2) {
if (list1->val < list2->val) {
tail->next = list1;
list1 = list1->next;
} else {
tail->next = list2;
list2 = list2->next;
}
tail = tail->next;
}
tail->next = list1 ? list1 : list2; // 处理剩余部分
return newhead->next;
}
// 寻找中间节点
ListNode* findMiddle(ListNode* head) {
ListNode* fast = head;
ListNode* slow = head;
while (fast->next && fast->next->next) {
fast = fast->next->next;
slow = slow->next;
}
return slow;
}
// 归并排序链表
ListNode* sortList(ListNode* head) {
if (head==NULL ||head->next==NULL)
return head; // 检查链表长度
// 找到链表的中间节点
ListNode* mid = findMiddle(head);
ListNode* right = mid->next;
mid->next = nullptr; // 切分链表
// 递归地对左右两部分进行排序
ListNode* l = sortList(head);
ListNode* r = sortList(right);
// 合并两个有序链表
return merge(l, r);
}
}
};
复杂度分析
-
时间复杂度： O(nlogn)
-
空间复杂度： O(logn)
