潍坊制作网站的公司,天元建设集团有限公司租赁公司,室内设计案例分享,电子商务网站建设哪家好少年的书桌上没有虚度的光阴 题目描述
请你对链表进行排序
思路分析 核心思想#xff1a;归并排序
有三个部分
链表排序实现
1. merge 函数
21.见 合并两个有序链表#xff0c; 首先创建一个虚拟头节点 newhead#xff0c;并使用指针 tail 来构建合并后的链表。 通过… 少年的书桌上没有虚度的光阴 题目描述
请你对链表进行排序
思路分析 核心思想归并排序
有三个部分
链表排序实现
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 (headNULL ||head-nextNULL) 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)
