单链表基本操作+归并排序（C/C++实现）

单链表视频中版本：

#include<bits/stdc++.h>
using namespace std;
struct Data_type{
    char name[15];
    int score;
    void out(){
        printf("(%s:%d)",name,score);
    }
};
bool operator ==(Data_type l, Data_type r){
    if(l.score!=r.score) return 0;
    if(strlen(l.name)!=strlen(r.name))return 0;
    int n=strlen(l.name);
    for(int i=0;i<n;i++){
        if(l.name[i]!=r.name[i])return 0;
    }
    return 1;
}
bool operator <(Data_type l, Data_type r){
    if(l.score!=r.score) return l.score>r.score;
    int n=max(strlen(l.name), strlen(r.name));
    for(int i=0;i<n;i++){
        if(l.name[i]!=r.name[i])return l.name[i]<r.name[i];
    }
    return 0;
}
struct Node{
    Data_type data;
    Node* next;
};
struct link_list{
    Node* head;
    int SIZE;
    void bulid(){
        head= new Node;
        head->next= NULL;
        SIZE=0;
    }
    int size(){
        return SIZE;
    }
    bool push(Data_type x, int k){
        if(size()<k) return 0;
        Node* now= head;
        while(k--){
            now= now->next;
        }
        Node* temp= new Node;
        temp->data= x;
        temp->next= now->next;
        now->next= temp;
        SIZE++;
        return 1;
    }
    void push_front(Data_type data){
        push(data, 0);
    }
    void push_back(Data_type data){
        push(data, size());
    }
    Node* find(int pos){
        if(size()<pos) return NULL;
        Node* ret= head;
        while(pos--){
            ret= ret->next;
        }
        return ret;
    }
    vector<int> query(Data_type data){
        vector<int>ret;
        int cnt=0;
        Node* now= head;
        while(now->next!=NULL){
            now= now->next;
            cnt++;
            if(now->data==data){
                ret.push_back(cnt);
            }
        }
        return ret;
    }
    void pop(int pos){
        if(pos<1||pos>size()){
            printf("error\n");
            return ;
        }
        Node* now= head;
        pos--;
        while(pos--){
            now= now->next;
        }
        Node* temp= now->next;
        now->next= now->next->next;
        delete(temp);
        SIZE--;
    }
    void pop_front(){
        pop(1);
    }
    void pop_back(){
        pop(size());
    }
    void print(Node* x){
        while(x!=NULL){
            printf("-->");
            x->data.out();
            x= x->next;
        }
    }
    void print(){
        Node* now= head;
        while(now->next!=NULL){
            now= now->next;
            printf("--> ");
            now->data.out();
        }
        printf("\n");
    }
    void clear(Node* x){
        if(x==NULL) return;
        clear(x->next);
        delete(x);
        SIZE--;
    }
    void clear(){
        clear(head);
    }
    Node* find_inv(int pos){
        if(pos>size()) return NULL;
        Node* ret= head, *now= head;
        while(pos--){
            now= now->next;
        }
        while(now!=NULL){
            now= now->next;
            ret= ret->next;
        }
        return ret;
    }
    void reverse(){
        if(size()<=0) return ;
        Node* now= head->next;
        while(now->next!= NULL){
            Node* temp= now->next;
            now->next= now->next->next;
            temp->next= head->next;
            head->next= temp;
        }
    }
    Node* Get_mid(Node* x){
        Node* mid=x, *p=x;
        while(p->next!=NULL&&p->next->next!=NULL){
            p= p->next->next;
            mid= mid->next;
        }
        Node* ret= mid->next;
        mid->next= NULL;
        return ret;
    }
    Node* merge(Node* x, Node* y){
        Node* ret=NULL, *tail=NULL;
        while(x!=NULL&&y!=NULL){
            if(x->data < y->data){
                Node* temp= x->next;
                if(ret==NULL){
                    ret= tail= x;
                    ret->next= NULL;
                }
                else {
                    tail->next= x;
                    tail= tail->next;
                    tail->next= NULL;
                }
                x=temp;
            }
            else{
                Node* temp= y->next;
                if(ret==NULL){
                    ret= tail= y;
                    ret->next= NULL;
                }
                else {
                    tail->next= y;
                    tail= tail->next;
                    tail->next= NULL;
                }
                y=temp;
            }
        }
        if(x!=NULL){
            tail->next= x;
        }
        else{
            tail->next= y;
        }
        return ret;
    }
    Node* sort(Node* x){
        if(x->next==NULL) return x;
        Node* mid= Get_mid(x);
        Node* p1= sort(x);
        Node* p2= sort(mid);
        return merge(p1, p2);
    }
    void sort(){
        head->next= sort(head->next);
    }
};
int main(){
    link_list ans;
    ans.bulid();
    Data_type temp;
    temp.name[0]='s';
    temp.name[1]='a';
    temp.name[2]='m';
    temp.name[3]='y';
    temp.name[4]='1';
    temp.name[5]='\0';
    temp.score=5;
    ans.push_front(temp);
    temp.name[4]='2';
    temp.score=15;
    ans.push_front(temp);
    temp.name[4]='3';
    temp.score=150;
    ans.push_back(temp);
    ans.print();
    ans.reverse();
    ans.sort();
    ans.print();
    return 0;
}
/* 小目标： 1.创建链表 ok 2.在链表头部插入元素x ok 3.在链表尾部插入元素x ok 4.在链表第k个元素后插入元素x ok 5.查询当前链表长度 ok 6.查询链表第k个元素 ok 7.查询链表中所有值为x的元素，返回vector ok 8.删除链表中的第k个元素（将空间释放） ok 9.删除链表头 ok 10删除链表尾 ok 11.清空链表 ok 12.链表翻转 ok 13.顺次输出整个链表 ok 14.查找链表中倒数第k个元素。（另写） ok 15.链表排序（O(nlogn)） ok */

数组归并排序：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10002;
int a[maxn],n,temp[maxn];
void sort(int l, int r){//[l,r)
    if(r-l==1){
        return ;
    }
    int mid=(l+r)/2;
    sort(l,mid);
    sort(mid,r);
    int pl=l, pr=mid, pos=l;
    while(pl<mid&&pr<r){
        if(a[pl]<a[pr]){
            temp[pos]= a[pl];
            pos++,  pl++;
        }
        else{
            temp[pos]= a[pr];
            pos++,  pr++;
        }
    }
    while(pl<mid){
        temp[pos]= a[pl];
        pos++,  pl++;
    }
    while(pr<r){
        temp[pos]= a[pr];
        pos++,  pr++;
    }
    for(int i=l;i<r;i++){
        a[i]=temp[i];
    }
}
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    sort(0,n);//[0,n)
    for(int i=0;i<n;i++){
        printf("%d ",a[i]);
    }
}
/* 1.将当前链表拆成两半 2.分别将两半链表排序好 3.将两个有序的链表合并成一个有序链表 */

单链表附加版本：

#include<bits/stdc++.h>
using namespace std;
struct Data_type{
    int score;
    char s[1];
    void print(){
        printf("( %s: %d )",s,score);
    }
};
bool operator ==(Data_type l, Data_type r){
    if(l.score!=r.score|| strlen(l.s)!=strlen(r.s))return 0;
    int n=strlen(l.s);
    for(int i=0;i<n;i++){
        if(l.s[i]!=r.s[i])return 0;
    }
    return 1;
}
bool operator <(Data_type l, Data_type r){
    if(l.score!= r.score)return l.score>r.score;
    int n= max( strlen(l.s), strlen(r.s) );
    for(int i=0;i<n;i++){
        if(l.s[i]!=r.s[i])return l.s[i]<r.s[i];
    }
    return 0;
}
struct Node{
    Data_type data;
    Node* next;
};
struct link_list{//链表
    Node* head;
    int SIZE;
    void build(){
        head=new Node;
        head->next= NULL;
        SIZE=0;
    }
    int size(){
        return SIZE;
    }
    void push_front(Data_type data){
        Node* now=new Node;
        now->data= data;
        now->next= head->next;
        head->next= now;
        SIZE++;
    }
    void push_back(Data_type data){
        Node* now=head;
        while(now->next!=NULL){
            now=now->next;
        }
        now->next= new Node;
        now= now->next;
        now->next= NULL;
        now->data= data;
        SIZE++;
    }
    bool push(Data_type data, int pos){//如果不存在第pos个，返回0
        if(SIZE<pos)return 0;
        Node* now= head;
        while(pos--){
            now=now->next;
        }
        Node* temp=now->next;
        now->next= new Node;
        now= now->next;
        now->next= temp;
        now->data= data;
        SIZE++;
        return 1;
    }
    Node* find(int pos){//找到正数第pos个
        if(pos>size()) return NULL;
        Node* ret=head;
        while(pos--){
            ret= ret->next;
        }
        return ret;
    }
    Node* find_inv(int pos){//找到倒数第pos个
        if(pos>size()) return NULL;
        Node* ret=head;
        Node* now=head;
        while(pos--){
            now= now->next;
        }
        while(now!=NULL){
            now= now->next;
            ret= ret->next;
        }
        return ret;
    }
    void print(){
        Node* now= head;
        while(now->next!= NULL){
            now=now->next;
            printf("-->");
            now->data.print();
        }
        printf("\n");
    }
    void print(int pos){
        Node* now= find(pos);
        if(now==NULL){
            printf("error\n");
            return;
        }
        printf("%d:",pos);
        now->data.print();
        printf("\n");
    }
    void print(Node* x){
        while(x!=NULL){
            printf("%d ",x->data.score);
            x=x->next;
        }
        printf("\n");
    }
    void pop(int pos){
        if(pos<1||pos>size()){
            printf("error\n");
            return;
        }
        Node* now= head;
        pos--;
        while(pos--){
            now= now->next;
        }
        Node* temp= now->next;
        now->next= now->next->next;
        delete(temp);
        SIZE--;
    }
    void pop_front(){
        pop(1);
    }
    void pop_back(){
        pop(size());
    }
    void clear(Node* x){
        if(x==NULL) return;
        clear(x->next);
        delete(x);
        SIZE--;
    }
    void clear(){
        clear(head);
    }
    vector<int> query(Data_type data){
        vector<int>ret;
        Node* now= head;
        int cnt=0;
        while(now->next!= NULL){
            now= now->next;
            cnt++;
            if(now->data== data){
                ret.push_back(cnt);
            }
        }
        return ret;
    }
    void link(link_list &x){//把x接到当前链表后面
        Node* now= head;
        while(now->next!= NULL){
            now= now->next;
        }
        Node* temp= x.head;
        now->next= temp->next;
        delete(temp);
        x.head= NULL;
    }
    void reverse(){
        if(size()==0)return ;
        Node* now= head->next;
        while(now->next!=NULL){
            Node* temp= now->next;
            now->next= now->next->next;
            temp->next= head->next;
            head->next= temp;
        }
    }
    Node* Get_mid(Node* x){
        Node* mid=x, *p=x;
        while(p->next!=NULL&& p->next->next!= NULL){
            p= p->next->next;
            mid= mid->next;
        }
        Node* ret= mid->next;
        mid->next= NULL;
        Node* test=x;
        return ret;
    }
    Node* merge(Node* x, Node* y){
        Node* ret=NULL, *tail=NULL;
        while(x!=NULL&& y!=NULL){
            if(x->data < y->data ){
                Node* temp= x->next;
                if(ret==NULL){
                    ret= tail= x;
                    ret->next= NULL;
                }
                else{
                    tail->next= x;
                    tail= tail->next;
                    tail->next= NULL;
                }
                x=temp;
            }
            else{
                Node* temp= y->next;
                if(ret==NULL){
                    ret= tail= y;
                    ret->next= NULL;
                }
                else{
                    tail->next= y;
                    tail= tail->next;
                    tail->next= NULL;
                }
                y=temp;
            }
        }
        if(x!=NULL){
            tail->next= x;
        }
        if(y!=NULL){
            tail->next= y;
        }
        return ret;
    }
    Node* sort(Node* x){
        if(x->next== NULL) return x;
        Node* mid= Get_mid(x);
        Node* p1=sort(x);
        Node* p2=sort(mid);
        return merge(p1, p2);
    }
    void sort(){
        head->next= sort(head->next);
    }

};
void test(){
    while(getchar()){
        int T=rand();
        int m=T;
        link_list ans;
        ans.build();
        Data_type add;
        while(T--){
            add.score=rand();
            ans.push_front(add);
        }
        ans.sort();
        int pre;
        Node* now=ans.head->next;
        for(int i=0;i<m;i++){
            if(i!=0){
                if(pre< now->data.score){
                    while(1)printf("error");
                }
            }
            pre=now->data.score;
            //printf("%d",now->data.score);
            now=now->next;
        }
        printf("%d ok\n",m);
    }
}
int main(){
    test();
    return 0;
}
/* 小目标： 1.创建链表 ok 2.向链表尾部插入元素 ok 3.向链表头部插入元素 ok 4.向链表第k个位置后面插入元素 ok 5.返回链表中元素个数 ok 6.清空链表（释放空间） ok 7.删除链表中第k个元素 ok 8.查询链表中第k个元素 ok 9.查询链表中值为x的元素个数，分别是链表中第几个 ok 10.输出链表中第k个元素 ok 11.将两个链表顺次连接 ok 12.将链表翻转 ok 13.找到链表中倒数第k个元素（这个其实没啥必要， 但是为了讲一种链表的操作思路，所以把它加了进来） ok 14.链表排序（时间复杂度O(nlogn)） ok 15.顺次输出链表 ok */