链表的转置（详细讲解）

链表转置：

解题思想：

1. 将头节点与当前链表断开，断开前保存下头节点的下一个节点，保证后面链表能找得到，定义一个q保存头节点的下一个节点，断开后前面相当于一个空的链表，后面是一个无头的单向链表。
2. 遍历无头链表的所有节点，将每一个节点当做新节点插入空链表头节点的下一个节点(头插)，插入之前先用t保存一下q的下一个节点以防插入完找不到原来链表。

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node
{
    datatype data;struct node *next;
} node_t, *node_p;//创建一个空的有头单向链表
node_p createEmptyLinkList() //create创建 Empty空的 LinkList单向链表
{//开辟链表节点大小空间
    node_p p = (node_p)malloc(sizeof(node_t));if (NULL == p){perror("createEmptyLinkList");return NULL;}//初始化头节点
    p->next = NULL;return p;
}//计算链表的长度。
int lengthLinkList(node_p p)
{int len = 0;while (p->next != NULL){
        p = p->next;
        len++;}return len;
}//向单向链表的指定位置插入数据
//p保存链表的头指针 post 插入的位置 data插入的数据
int insertIntoPostLinkList(node_p p, int post, datatype data)
{//(1)容错判断if (post < 0 || post > lengthLinkList(p)){printf("insertIntoPostLinkList err\n");return -1;}    node_p pnew = NULL; //记录新节点//（2）将指针 遍历到插入位置的前一个节点for (int i = 0; i < post; i++)
        p = p->next;//（3）malloc创建一个新节点， 初始化新节点
    pnew = (node_p)malloc(sizeof(node_t));if (NULL == pnew){perror("insertIntoPostLinkList err");return -1;}
    pnew->data = data;
    pnew->next = NULL;//（4）连接新节点到链表， 先连后面，再连前面。(不然前面断了后面就找不到了)
    pnew->next = p->next;
    p->next = pnew;return 0;
}//遍历单向链表
void showLinkList(node_p p)
{while (p->next != NULL){
        p = p->next;printf("%d ", p->data);}printf("\n");
}//判空，为空返回1，不为空返回0
int isEmptyLinkList(node_p p)
{return p->next == NULL;
}//删除单向链表中指定位置的数据 post 代表的是删除的位置
int deletePostLinkList(node_p p, int post)
{
    node_p pdel = NULL;//  (1)容错判断：判空||post<0 || post >=长度if (isEmptyLinkList(p) || post < 0 || post >= lengthLinkList(p)){printf("deletePostLinkList err\n");return -1;}// (2) 将指针遍历到删除位置的前一个节点for (int i = 0; i < post; i++)
        p = p->next;// (3)设指针pdel记录要删除节点:pdel = p->next;
    pdel = p->next;// (3)跨过要删除节点：p->next = pdel->next; (或者p->next = p->next->next;)
    p->next = pdel->next;// (4)释放要删除节点: free(pdel); pdel=NULL;free(pdel);
    pdel = NULL;return 0;
}//思想：
// 循环进行删除，每次删除的头节点的下一个节点：
// (1)定义一个pdel,指向被删除节点
// (2)跨过被删除节点
// (3)释放被删除节点
void clearLinkList(node_p p)
{
    node_p pdel = NULL;while (p->next != NULL){
        pdel = p->next;
        p->next = pdel->next;free(pdel);
        pdel = NULL;}
}//修改链表中指定的数据
int changePostLinkList(node_p p, int post, datatype data)
{//  (1)容错判断：判空||post<0 || post >=长度if (isEmptyLinkList(p) || post < 0 || post >= lengthLinkList(p)){printf("changePostLinkList err\n");return -1;}// (2) 将指针移动到 要修改节点for (int i = 0; i <= post; i++)
        p = p->next;//(3) 修改数据
    p->data = data;return 0;
}//查找指定数据出现的位置 data被查找的数据 //search 查找
int searchDataLinkList(node_p p, datatype data)
{int post = 0; //记录查找节点的位置while (p->next != NULL){
        p = p->next;if (p->data == data)return post;
        post++;}return -1; //说明数据不存在
}//删除单向链表中出现的指定数据,data代表将单向链表中出现的所有data数据删除
//思想：p始终指向被删除节点的前一个，让q相当于遍历无头节点，q用于指向删除节点。
int deleteDataLinkList(node_p p, datatype data)
{
    node_p q = p->next; //跳过头节点, 用于遍历无头单向链表while (q != NULL)   //相当于遍历无头单向链表{if (q->data == data) //判断是否是要删除的节点{//删除：//(1)跨过要删除节点
            p->next = q->next;//(2)释放删除节点free(q);
            q = NULL;//让q继续指向p的下一个节点，以便 继续向后遍历
            q = p->next;}else{//继续向后遍历，让q和p指针都向后走一个
            q = q->next;
            p = p->next;}}
}//链表转置：利用头插实现
void reverseLinkList(node_p p) //reverse反向
{
    node_p t = NULL;    //用来临时保存q的下一个节点，以防头插以后找不到原来链表。
    node_p q = p->next; //断头前定义指针q保存头节点的下一个，用于遍历无头链表
    p->next = NULL;     //断开头节点while (q != NULL)   //用q遍历无头链表，遍历一个节点头插一个{//头插q之前让t指针保存q的下一个，以防下次循环找不到链表
        t = q->next;//将q所指节点头插：先连后面再连前面
        q->next = p->next;
        p->next = q;//让q找t继续向后遍历进行头插
        q = t;}
}int main(int argc, char const *argv[])
{
    node_p p = createEmptyLinkList();for (int i = 0; i < 5; i++)insertIntoPostLinkList(p, i, i);showLinkList(p); //0 1 2 3 4insertIntoPostLinkList(p, -1, 10); //insertIntoPostLinkList err 容错判断打印结果deletePostLinkList(p, 1);showLinkList(p); //0 2 3 4changePostLinkList(p, 1, 1000);showLinkList(p); //0 1000 3 4insertIntoPostLinkList(p, 4, 1000);showLinkList(p); //0 1000 3 4 1000deleteDataLinkList(p, 1000);showLinkList(p);    //0 3 4reverseLinkList(p); //4 3 0showLinkList(p);clearLinkList(p);printf("%d\n", isEmptyLinkList(p)); //1return 0;
}