织梦淘客网站,跨境外贸网,wordpress的登录地址修改,建设网站的工作题目
给你链表的头结点 head #xff0c;请将其按 升序 排列并返回 排序后的链表 。
示例 输入#xff1a;head [4,2,1,3] 输出#xff1a;[1,2,3,4] 输入#xff1a;head [-1,5,3,4,0] 输出#xff1a;[-1,0,3,4,5] 输入#xff1a;head [] 输出#xff1a;[] 思路…题目
给你链表的头结点 head 请将其按 升序 排列并返回 排序后的链表 。
示例 输入head [4,2,1,3] 输出[1,2,3,4] 输入head [-1,5,3,4,0] 输出[-1,0,3,4,5] 输入head [] 输出[] 思路
对于链表排序我们可以使用链表的归并排序Merge Sort算法。下面是整体的思路 归并排序的核心思想归并排序是一种分治算法首先将待排序的链表分成两部分然后分别对这两部分进行排序最后将排好序的两部分链表合并起来。 mergeSort 函数这个函数是归并排序的入口负责调用递归排序的函数 mergeSort并返回排好序的链表。在 mergeSort 中首先判断链表是否为空或只有一个节点如果是则直接返回原链表。然后找到链表的中间节点 mid将链表分成左右两部分分别以 head 和 mid-next 开始。然后分别对左右两部分链表调用 mergeSort 递归排序最终通过 merge 函数将排好序的两部分链表合并。 findMid 函数这个函数用快慢指针的方法找到链表的中间节点快指针每次移动两步慢指针每次移动一步当快指针到达链表末尾时慢指针指向的节点即为中间节点。 merge 函数这个函数用于合并两个有序链表。创建一个虚拟头节点 dummyHead 和一个指针 cur遍历两个链表的节点根据节点值的大小依次连接到 cur-next 上然后将 cur 移动到下一个节点。最后将剩余未遍历完的链表连接到 cur-next 上。返回虚拟头节点的下一个节点即为合并后的有序链表。
综上所述这段代码通过归并排序算法对链表进行排序利用分治和合并的思想最终得到一个按升序排列的链表。
Code
class Solution {
public:ListNode* sortList(ListNode* head) {return mergeSort(head);}ListNode* mergeSort(ListNode* head) {if (!head || !head-next) return head;ListNode* mid findMid(head);ListNode* l1 head;ListNode* l2 mid-next;mid-next nullptr;l1 mergeSort(l1);l2 mergeSort(l2);return merge(l1, l2);}ListNode* findMid(ListNode* head) {ListNode *slow head, *fast head;while (fast-next fast-next-next) {slow slow-next;fast fast-next-next;}return slow;}ListNode* merge(ListNode* l1, ListNode* l2) {// l1 l2长度ListNode* dummyHead new ListNode();ListNode* cur dummyHead;while (l1 l2) {if (l1-val l2-val) {cur-next l1;l1 l1-next;}else {cur-next l2;l2 l2-next;}cur cur-next;}cur-next l1 ? l1 : l2;return dummyHead-next;}
};
