链表中进行排序的归并算法

清疚 2022-11-22 10:16 112阅读 0赞

链表排序的核心就是断链+合并链表

主要涉及到的操作是统计链表长度(来判断最大的合并步长) 分割链表 将两个链表进行合并

/*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) {}
      };*/
    
    ListNode* sortList(ListNode* head) {
            
            /* 此为归并算法进行求解
            if(!head) return nullptr;  //此判断仅用来排除[]测试点
            //尝试采用递归的归并排序进行解题
            //使用快慢指针找到中间结点
            ListNode *p,*q;
            p=head;
            q=head->next;
            if(!q) return p;  //只有一个结点
            while(q && q->next){
                p=p->next;
                q=q->next->next;
            }
            //将链表断开
            q=p->next; 
            p->next=nullptr;
    
            head=sortList(head);
            q=sortList(q);
            return Merge(head,q);
            */
    
            //使用迭代归并进行排序
            ListNode *_head=new ListNode;
            _head->next=head;
            int count=count_len(head);
            ListNode *cur,*pre;
            for(int i=1;i<count;i*=2){
                pre=_head; cur=_head->next;  //进行初始化
                while(cur!=nullptr){
                    ListNode *h1=cur;
                    ListNode *h2=cut_list(h1,i);
                    cur=cut_list(h2,i);
                    h1=Merge(h1,h2);
                    pre->next=h1;
                    while(pre->next){
                        pre=pre->next;
                    }
                }
                //print(_head->next);
            }
            return _head->next;
        }
        //测试打印输出
        /*void print(ListNode *head){
            while(head){
                cout<<head->val<<" ";
                head=head->next;
            }
            cout<<endl;
        }*/
    
        //分割链表
        ListNode* cut_list(ListNode *head,int step){
            if(!head) return nullptr;
            ListNode *p,*q;
            p=head;
            for(int i=1;i<step && p->next!=nullptr;i++){  //此处应该当心最后剩下的链表不足分割  使用p->next判断的优点是即使不足分割 其代码形式和能够完整分割相同
                p=p->next;
            }
            q=p->next;
            p->next=nullptr;
            return q;
        }
        //获取链表的长度
        int count_len(ListNode *head){
            int count=0;
            while(head){
                head=head->next;
                count++;
            }
            return count;
        }
    
        //将两个链表进行归并
        ListNode* Merge(ListNode *head,ListNode *q){
            ListNode *_head=new ListNode;
            ListNode *p1,*p2,*tem;
            p1=head; p2=q; tem=_head;
            while(p1 && p2){
                if(p1->val <= p2->val){
                    tem->next=p1;
                    p1=p1->next;
                }
                else{
                    tem->next=p2;
                    p2=p2->next;
                }
                tem=tem->next;
            }
            if(p1) tem->next=p1;
            else tem->next=p2;
            return _head->next;
        }
    }