题解 | #字符串排序#

#include <iostream>
#include<string>
using namespace std;

class Node{
    public:
    int data;
    int UD;
    Node *next;
    Node(int a,int b,Node *p){
        this->data=a;
        this->UD=b;
        this->next=p;
    }
};

int main() {
    string s;
    int len,i,j,a,b;
    Node *head;
    Node *R;
    Node *re,*ne;
    getline(cin,s);
    len=s.length();
    i=0;
    while(1){
        if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')) break;
        i++;
    }
    if((s[i]>='a'&&s[i]<='z')) head=new Node(s[i]-'a',1,nullptr);
        else head=new Node(s[i]-'A',0,nullptr);
    for(i++;i<len;i++){
        if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')){
            if((s[i]>='a'&&s[i]<='z')) {
                a=s[i]-'a';
                b=1;
            }
            else{
                a=s[i]-'A';
                b=0;
            }
            if(a<(head->data)) {
                R=new Node(a,b,head);
                head=R;
                continue;
            }
            re=head;
            ne=head->next;
            while((ne!=nullptr)&&a>=(ne->data)){
                re=re->next;
                ne=ne->next;
            }
            R=new Node(a,b,ne);
            re->next=R;
        }
    }

    for(i=0;i<len;i++){
        if((s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')){
            if(head->UD==0) cout<<char(head->data+'A');
                else cout<<char(head->data+'a');
            head=head->next;
        }
        else cout<<s[i];
    }
    return 0;
}
// 64 位输出请用 printf("%lld")

好神经的做法，还错了一次，(ne!=nullptr)&&a>=(ne->data)注意判断顺序