c++ - leetcode 148. Sort List ，我想用stl里面list特有的sort解法来做，结果有问题

问题描述

问 题

这是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 ;
    }
};

解决方案

merge里修改s2为NULL并没有效果。
然后在sortList合并时会出现混乱

这篇关于c++ - leetcode 148. Sort List ，我想用stl里面list特有的sort解法来做，结果有问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！