荣成网站制作公司,专门做ppt的网站名称,湖南电商平台网站建设,大宗交易的套路你懂吗思路#xff0c;本题其实考察了两个点#xff1a;合并链表、链表切分。首先从1开始#xff0c;将链表切成一段一段#xff0c;因为需要使用归并#xff0c;所以下一次的切分长度应该是当前切分长度的二倍#xff0c;每次切分#xff0c;我们拿出两段#xff0c;然后将第…思路本题其实考察了两个点合并链表、链表切分。首先从1开始将链表切成一段一段因为需要使用归并所以下一次的切分长度应该是当前切分长度的二倍每次切分我们拿出两段然后将第三段的开头赋值给一个指针合并前面两段下一次继续从第三段开始切分然后继续合并。 trick:::链表设置虚拟头结点dummyhead这样对链表来说第一个元素就是dummyhead的next所对应的节点元素而不是dummyhead所对应的节点元素。dummyhead位置所对应的元素是根本不存在的这只是未来我们编写逻辑方便而出现的一个虚拟头结点。dummyhead就是索引为0的这个位置的元素的前一个节点。当我们有了dummyhead后为链表添加一个元素就不需要对头结点进行特殊处理了只需要找到等待添加位置的前一个位置的节点
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode() : val(0), next(nullptr) {}* ListNode(int x) : val(x), next(nullptr) {}* ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* sortList(ListNode* head) {// 定义虚拟头节点注意这里不是结构体指针类型ListNode dummyhead(0);// 指针处理这里使用点而不是箭头,虚拟头节点之后的节点是头节点dummyhead.next head;int len 0;ListNode *p head;// 计算链表长度while(p){len;p p - next;}// 开始切割链表从短的开始逐渐合成长的// 注意size每次增加长度为之前的两倍(左移一位)for(int size 1;size len;size 1){ListNode *cur dummyhead.next;ListNode *tail dummyhead;while(cur){// 切下来一段链表节点ListNode *left cur;// right是下一段链表的初始节点ListNode *right cut_list(left, size);// 从下一段链表开始继续切cur cut_list(right, size);// 切分之后开始进行合并,比如首先合并left,right为首的这两段tail - next merge(left, right);// 当下一个位置不为空的时候继续进行游走直到合并好的链表的末尾while(tail - next){tail tail - next;}}}return dummyhead.next;}ListNode *cut_list(ListNode *head, int n){int size n;ListNode *p head;// 如果需要切的size是1那么就不需要裁切所以首先对size进行自减while(--size p){p p - next;} // 如果走到头了就返回空if(p nullptr)return nullptr;// 如果不为空就把p节点之后的节点进行处理ListNode *next p - next;p - next nullptr;// 返回被切分的下一个节点的位置return next;}ListNode *merge(ListNode *l1, ListNode *l2){// 虚拟头节点ListNode dummyhead(0);ListNode *p dummyhead;// 当二者都不为空的时候开始归并while(l1 l2){// 选择较小的进行尾插if(l1 - val l2 - val){p - next l1;p p - next;// 尾插结束之后游标后移l1 l1 - next;}else{p - next l2;p p - next;// 尾插结束之后游标后移l2 l2 - next;}}if(l1)p - next l1;if(l2)p - next l2;// 因为是虚拟头节点所以返回第一个数据节点return dummyhead.next;}
};
