问题描述
这是stl中容器list成员函数sort的实现
void sortList(list<int> &a) { if(a.size() <= 1){return; }list<int> carry; // 辅助链表，用于从a中提取元素以及临时保存两个链表的合并结果 list<int> counter[64]; // 保存着当前每一个归并层次的结果, i号链表保存的元素个数为2的i次方或者0 int fill = 0; // 表示当前最大归并排序的层次，while循环之后fill变成log2(a.size())while (!a.empty()) {carry.splice(carry.begin(), a, a.begin()); // 将链表a中的第一个元素移动至carry开头int i = 0;// 从小往大不断合并非空归并层次直至遇到空层或者到达当前最大归并层次while (i < fill && !counter[i].empty()) { counter[i].merge(carry); // 链表合并，结果链表是有序的，必须保证合并前两个链表是有序的 carry.swap(counter[i++]); // 链表元素互换}carry.swap(counter[i]);if (i == fill) { // i到达当前最大归并层次，说明得增加一层 ++fill;} }for (int i = 1; i < fill; ++i) { // 将所有归并层次的结果合并得到最终结果counter[fill - 1]counter[i].merge(counter[i - 1]); } a.swap(counter[fill - 1]);}
我想仿照这种做法，即链表的归并迭代方式，来求解leetcode148题https://leetcode.com/problems...但是无法实现，下面是我的代码另外我已经做了链表的归并递归方法，我觉得迭代应该更优，想尝试一下
class Solution {public: ListNode* sortList(ListNode* head) {if(!head||!head->next)return head;ListNode*carry=NULL;ListNode*count[64];int fill=0;while(head){ carry=new ListNode(head->val); head=head->next; int i=0; while(i<fill&&!count[i]){merge(count[i],carry);swap(carry,count[i]);i++; } swap(carry,count[i]); if(i==fill){fill++; }}for(int i=1;i<fill;i++){ merge(count[i],count[i-1]);}return count[fill-1]; }private://模仿链表容器的merge成员函数//将链表s2合并入s1中，默认s1，s2都是sorted，并且最后s2为NULL void merge(ListNode*s1,ListNode*s2){if(!s1){ auto temp=s2; s2=NULL; s1=s2; return;}ListNode* dump=new ListNode(-1);ListNode* newHead;newHead=dump;if(!s2)return;while(s1&&s2){ if(s1->val<s2->val){newHead->next=s1;s1=s1->next; } else{newHead->next=s2;s2=s2->next; } newHead=newHead->next;}if(s1)newHead->next=s1;else if(s2)newHead->next=s2;s2=NULL;s1=dump->next;delete dump;return ; }};
问题解答
回答1：merge里修改s2为NULL并没有效果。然后在sortList合并时会出现混乱
