链表算法总结

针对考研王道上的链表题目，总结出几个经典的链表算法，更新中。。。

//结构体
struct ListNode {
    int data;
    struct ListNode *next;
};

//建立
ListNode* readlist(){   //按照读入顺序建立链表，尾插法(带头结点)
    int n;
    ListNode *s=NULL,*L=NULL;
    while(1){
        ListNode* temp=(ListNode*)malloc(sizeof(ListNode)); //建立新的结点 
        scanf("%d",&n);
        if(n==-1) break;
        temp->data=n;
        temp->next=NULL;
        if(L==NULL){
            L=temp;
        }
        else{
            s->next=temp;
        }
        s=temp;
    }
    return L;

}

//删除链表中值为m的结点(带头结点的链表) 
ListNode *deletem( ListNode *L, int m ){
    ListNode *p,*q;  //move用于往下走，q用于删除时用 
    while(L&&L->data==m){  //如果头结点的值刚好为m 
        q=L;
        L=L->next;
        free(q);
    }
    p=L;
    while(p && p->next){     //p必须有
        if(p->next->data==m){
            q=p->next;
            p->next=q->next;
            free(q);
        }
        else{
            p=p->next;
        } 
    }
    return L;
    
}

//将链表排序(简单选择排序) 
ListNode* selectsort(ListNode* L){
    ListNode *p,*q,*small;  //p为当前结点，从p往下找最小的结点small 
    for(p=L;p->next!=NULL;p=p->next){ //一直往下遍历 
        small=p;
        for(q=p->next;q;q=q->next){  //循环条件看一看 
            if(q->data < small->data){
                small=q;
            }
        }
        if(small!=p){  //将small与p结点的值交换 
            int temp=p->data;
            p->data=small->data;
            small->data=temp;
        }
    } 
    return L;
    
} 

ListNode* reverse(ListNode* head){   //反转链表，适合头结点也有结点的情况 
    ListNode* pre=NULL;
    ListNode* curr=head;
    while(curr){
        ListNode* next=curr->next;
        curr->next=pre;
        pre=curr;
        curr=next;
    }
    return pre;   //不能返回curr，此时是NULL 
}