一、初始化单链表

初始化一个带头结点的单链表，需要一个数据域和一个指针域

typedef struct node{
    int data;        //数据域
    struct node * next;    //指针域
}node,*pnode;
pnode init_node(){
    pnode head=(pnode)malloc(sizeof(node));
    head->next=NULL;
}

二、插入

单链表的插入操作，不需要担心空间不足的情况，我们需要先找到插入的位置，然后再执行插入操作，注意这里我们要找的是需要插入位置的前面一个结点，这样子方便我们进行插入操作，插入操作的具体步骤为：找到插入位置前一个结点——>判断插入位置是否合法——>新建一个要插入的结点——>将该新结点插入进单链表

int insert_node(pnode head,int i,int e){
    pnode p=head;       //头结点
    int j=0;
    while(p&&j<i-1){    //获取插入位置前面一个结点
        p=p->next;
        j++;
    }
    if(!p||j>i-1){     //判断是否合法
        return 0;
    }
    pnode pnew=(pnode)malloc(sizeof(node));  //新建一个结点
    pnew->data=e;                  
    pnew->next=NULL;    
    pnew->next=p->next;       //插入单链表中
    p->next=pnew;
    return 1;
}

三、删除

单链表的删除操作，同插入操作一样，我们需要先找到删除的位置，然后执行删除，具体步骤为：找到删除位置的前一个结点——>判断要删除的位置是否合法——>删除该结点

int delete_node(pnode head,int pos,int *val){
    pnode p=head;         //头结点
    int j=0;            
    while(p&&j<pos-1){    //找到要删除元素的前面一个结点
         p=p->next;
        j++;
    }
    if(!p||j>pos){     //判断是否合法
        return 0;
    }
    pnode s;
    s=p->next;        //s存放要删除的结点
    *val=s->data;     //val存放要删除结点的数据域，便于输出
    p->next=s->next;    //删除
    free(s);          //释放内存
    return 1;
}

四、查找

单链表的查找操作，同插入删除操作一样，需要找位置，但是不同的是，这里我们直接找该结点的位置即可，不需要用到它前面的结点

4.1 按位查找

按位查找，只需要通过循环得到要查找结点的位置即可，利用val保存该结点的数据域，便于输出查找的结点值

int find1_node(pnode head,int pos,int *val){
    int i=0;
    pnode p=head;
    while(p&&i<pos){    //找到要查找的结点
        p=p->next;
        i++;
    }
    if(!p||i>pos){     //判断是否合法
        return 0;
    } 
    *val=p->data;     //val保存该节点数据域，便于输出
    return 1;
}

4.2 按数查找

按数查找，我们利用循环即可得到要查找结点的位置

int find2_node(pnode head,int *pos,int val){
    pnode p=head;
    int i=0;
    while(p){       //循环，找到val，输出位置
        if(val==p->data){
            *pos=i+1;
            break;
        }
        p=p->next;
        i++;
    }
    return 0;
}

五、逆置

1、单链表的逆置操作，我们需要三个指针，一个指向头结点后面的第一个有效结点，一个指向第二个有效结点，还有一个指向第三个有效结点
2、逆置的具体步骤为：将第一个有效结点q与后面断开，q变成了该单链表逆置后的尾结点——>将第二个有效结点p连接到头结点后面——>将第三个有效结点r给p继续循环放到头结点后面——>得到逆置后的单链表

int nizhi_node(pnode head){
    pnode p,q,r;       //p,q,r三个指针
    p=head->next;
    q=p->next;            
    p->next=NULL;      //断开单链表，将单链表分为两个部分
    while(q){          //循环
        r=q->next;     //有点像头插法
        q->next=head->next;
        head->next=q;
        q=r;
    }
}

六、排序

单链表的排序算法，就是利用双重循环，第一重循环是遍历单链表的所有结点，第二重循环用来判断，寻找有没有数据域相同的结点，如果有，删除；如果没有，执行下一重循环

int sort_node(pnode head){
    pnode p,q;
    int t;
    for(p=head->next;p;p=p->next){    //第一重循环，遍历单链表
        for(q=p->next;q;q=q->next){    //第二重循环，进行排序
            if(p->data>q->data){
                t=p->data;
                p->data=q->data;
                q->data=t;
            }
        }
    }
}

七、删除指定数

1、单链表删除指定大于x小于y的数，我们需要两个指针，一个指向头结点，还有一个指向头结点后面第一个有效结点
2、删除的方法为：循环判断如果存在结点的数据域大于x并且小于y，则将该结点删除（p始终是q前面的那个结点，方便删除）

int delete1_node(pnode head,int x,int y){
    pnode p=head;
    pnode q=head->next;
    while(q){
        if(q->data>x&&q->data<y){    
            p->next=q->next;      //找到就删除
            pnode s=q;
            q=q->next;
            free(s);
        }else{
            p=p->next;    //p始终是q前面的那个结点
            q=q->next;
        }
    }
}

八、交换位置

单链表将指定位置的结点与其后面的一个结点交换位置，分为两种情况，一种是按位交换，还有一种是按数交换

8.1 按位交换

按位交换，我们先通过循环找到要交换的位置，然后执行交换

int jiaohuan1_node(pnode head,int pos){
    int i=0;
    pnode p=head;
    while(p&&i<pos-1){     //先找到要交换的位置
        p=p->next;
        i++;
    }
    if(!p||i>pos-1){       //判断位置是否合法
        return 0;
    }
    pnode s=p->next;       //执行交换
    pnode r=s->next;
    s->next=r->next;
    p->next=r;
    r->next=s;
}

8.2 按数交换

按数交换，我们先通过循环找到该元素的位置，然后执行交换

int jiaohuan2_node(pnode head,int val){
    pnode p,q,r;
    p=head->next;
    while(p){
        q=p->next;
        if(q->data==val){        //找位置，交换，思想一样
            break;
        }
        p=p->next;
    }
    r=q->next;
    q->next=r->next;
    p->next=r;
    r->next=q;
}

九、求单链表长度

单链表求长度，使用循环即可得到

int len_node(pnode head){
    int len=0;
    pnode p=head->next;
    while(p){       //循环
        len++;      //单链表长度加1
        p=p->next;
    }
    return len;
}

十、修改

单链表的修改操作，分为两种情况，一种是按位修改，另一种是按数修改

10.1 按位修改

按位修改，先通过循环找到要修改的结点，然后直接进行修改就好啦

int change1_node(pnode head,int pos,int val){
    pnode p=head;
    int i=0;
    while(p&&i<pos){    //找位置
        p=p->next;
        i++;
    }
    if(!p&&i>pos){
        return 0;
    }
    p->data=val;       //修改
    return 1;
}

10.2 按数修改

按数修改，也是通过循环找到结点，再执行修改操作就好啦

int change2_node(pnode head,int val1,int val2){
    pnode p=head->next;
    while(p){
        if(p->data==val1){   //找相同元素，直接修改
            p->data=val2;
        }
        p=p->next;
    }
}

十一、最大值

单链表输出最大值，我们直接通过循环找到最大值就好啦

int max_node(pnode head){
    int max;
    pnode p=head->next;     
    max=p->data;
    while(p){            //循环判断，找出最大值
        if(max<p->data){
            max=p->data;
        }
        p=p->next;
    }
    return max;
}

十二、按序插入

单链表按序插入结点，运用循环找到要插入的位置的前面一个结点，执行插入操作即可

int insert_sort_node(pnode head,int x){
    pnode p=head;
    pnode pnew=(pnode)malloc(sizeof(node));
    pnew->data=x;
    pnew->next=NULL;
    while(p->next->data<x&&p->next!=NULL){   //循环找到要插入位置的前一个结点
        p=p->next;
    }
    pnew->next=p->next;
    p->next=pnew;
}

十三、删除重复值

单链表删除重复值，我们需要两个指针，一个指向要删除的结点，另一个指向要删除结点的前面一个结点，我们运用循环找到相同的结点，执行删除操作即可

int delete_same_node(pnode head){
    pnode p,q;         //两个指针
    p=head->next;
    while(p){
        q=p;
        while(q->next){      
            if(p->data==q->next->data){    //遇到相同的就执行删除操作
                pnode s=q->next;
                q->next=s->next;
                free(s);
            }else{
                q=q->next;          
            }
        }
        p=p->next;
    }
}

单链表的十三个基本操作（全）