企业网站设计费做哪个科目,太原网络推广哪家好,汉化wordpress插件,网站打开是建设中文章目录 1. 题目描述2. 解题思路3. 代码实现 1. 题目描述 2. 解题思路 按我们以往的排序算法来看#xff0c;针对链表来说都是太不合适#xff0c;因为很多都会出现指针前移后移#xff0c;后移还好说#xff0c;前移对于链表来说就太难了#xff0c;而且大部分都是某一个… 文章目录 1. 题目描述2. 解题思路3. 代码实现 1. 题目描述 2. 解题思路 按我们以往的排序算法来看针对链表来说都是太不合适因为很多都会出现指针前移后移后移还好说前移对于链表来说就太难了而且大部分都是某一个位置和另一个离它很远的位置进行比较交换位置这在链表中是不切实际的。 但是其中的归并非常的适合链表相信大家也做过合并两个排序的链表和合并k个已排序的链表其实针对于单个链表的排序归并也是非常合适的因为其底层其实是两个挨着的结点进行排序的。 其原理就是先通过递归将一个链表分成一个一个单个的结点然后两两进行比较、排序、连接这是第一次排序再往后就是具有两个结点的链表和另一个具有两个结点的链表进行排序那么此时问题就是合并两个排序的链表了。 这样我们就完成了一个链表的排序。那么现在的问题就是如何分隔链表呢 就是通过递归在单次中我们使用leftmidright三个指针 left和mid一次走一步right一次走两步这样当right到最后一个结点时mid就在中间然后再让left-next指向nullptr断开两个链表。这样再对左右两个链表递归下去就完成了链表的分隔。当分隔成一个结点的时候就会开始排序。 在我八大排序的博客中的归并排序中有详细的分隔过程想了解的可以点击跳转。
3. 代码实现
/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) : val(x), next(nullptr) {}* };*/
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param head ListNode类 the head node* return ListNode类*/ListNode* Merge(ListNode* head1, ListNode* head2){if(head1 nullptr) return head2;if(head2 nullptr) return head2;auto ret new ListNode(-1);auto head ret;while(head1 head2){if(head1-val head2-val){ret-next head1;head1 head1-next;}else {ret-next head2;head2 head2-next;}ret ret-next;}if(head1) ret-next head1;if(head2) ret-next head2;return head-next;}ListNode* sortInList(ListNode* head) {if(head nullptr || head-next nullptr)return head;ListNode* left head, *mid head-next, *right head-next;while(right right-next){left left-next;mid mid-next;right right-next-next;}left-next nullptr;return Merge(sortInList(head), sortInList(mid));}
};
