单链表逆置

单链表的逆置（头插法，就地逆转）1.头插法，将链表中的每个元素都插到链表头部，进⾏逆转。

void reverse1(Node*head)
{//头插法逆转单链表
Node*p,*q;
p=head->next;
head->next=NULL;
while(p)
{
q=p;
p=p->next;
q->next=head->next;
head->next=q;
}
}
2.就地逆置，将链表中的指针指向改变，最后将head指向链表最后⼀个元素(逆置后的第⼀个)。

void reverse2(Node*head)
{//就地逆转法
Node *p, *s, *t;
p = head; // p开始指向头结点的
s = p->next; // s最开始是指向第⼀个节点的
while ( s->next != null ) // 没有到最后⼀个节点就继续
{
t = s->next; // ⽤t指向s后⾯的⼀个节点
s->next = p; // 把s指向的那个节点想在转换成指向它前⾯的那个节点，这个时候就实现了逆序，⽽且是就地逆序
p = s; // p向后移动到s的位置
s = t; // s向后移动到t的位置，这时候完成了第⼀步的置序，后⾯继续重复之前的动作就OK了
}
head->next = null;
head->next = s;
}。

C语⾔单链表逆置的代码实现（简单易懂版） 嗯，，这是⾃⼰写的第⼀篇博客哈，写的不好⼤家不要见怪，主要是想把⾃⼰的⼀些思想分享给⼤家。

也欢迎⼤家指出错误，⼀同进步。

话不多说，直接先说想法。

要把⼀个单链表逆置，可以⼤致分为下列⼏步。

先创建⼀个链表。

然后要考虑到链表的逆置实现。

最后是链表的输出。

有了这样过⼏步⼤概的想法之后，我们便要来⼀步步的实现啦。

嗯，，创建链表就不说了，⼤家都会。

然后呢就是链表的逆置，这⾥我是采⽤的就地逆置法，，嗯，反正我是这么叫的，⼤家可以参考⼀下。

当然啦，你得考虑到函数的形参和返回值以及指针的交接，这⾥如果出了问题，编译器是不会报错的，所以⼤家务必多加注意。

其余的⼩问题还是看代码吧。

额，，之前画的草图不见了，，现在也没有办法给⼤家画个草图演⽰⼀下，很抱歉啊。

如果⼤家看不懂链表逆置可以画个草图⾃⼰看看，应该就差不多了1 #include <stdio.h>2 #include <stdlib.h>34struct student5 {6int data;7struct student *next;8 };910int iCount; //定义全局变量保存代码长度1112struct student *Create()13 {14struct student *pHead = NULL;15struct student *pNew,*pEnd;16 iCount = 0;17 pEnd = pNew = (struct student*)malloc(sizeof(struct student));18 printf("请输⼊数据:");19 scanf("%d",&pNew->data);20while(pNew->data!=0)21 {22 iCount++;23if(iCount == 1) //从本条if语句开始就要多注意指针的交接了哦，⽐较容易错24 {25 pNew->next = NULL;26 pEnd = pNew;27 pHead = pNew;28 }29else30 {31 pNew->next = NULL;32 pEnd->next = pNew;33 pEnd = pNew;34 }35 pNew = (struct student*)malloc(sizeof(struct student));36 printf("请输⼊数据:");37 scanf("%d",&pNew->data);38 }39free(pNew);40return pHead;41 }4243struct student *reverse(struct student *pHead) //链表逆置函数44 {45struct student *p,*q,*t; //p为前置指针，q为后置指针，t为交换指针46 q = pHead;47 p = (q->next);48 q->next = NULL;49while(t!=NULL)50 {51 t = p->next;52 p->next = q;53 q = p;54if(t!=NULL) p = t;55else;56 }57return (p);58 }5960void showlist(struct student *pHead) //指针输出函数61 {62struct student *temp;63 temp = pHead;6465while(temp)66 {67 printf(" %d ",temp->data);68 temp = temp->next;69 }70 printf("\n");71 }7273int main()74 {75struct student *first;7677 first = Create();78 printf("链表逆置前的数据:");79 showlist(first);8081 first = reverse(first);8283 printf("链表逆置后的数据:");84 showlist(first);8586return0;87 }。

单链表原地逆置算法单链表是一种常见的数据结构，其操作包括插入、删除和查找等。

在实际应用中，有时需要将单链表进行逆置操作。

逆置操作的实现方式有多种，其中一种是原地逆置。

原地逆置是指在不使用额外空间的情况下，将单链表逆置。

具体实现方式如下：1. 定义三个指针：pre、cur、next，分别指向当前节点的前一个节点、当前节点和当前节点的后一个节点。

2. 将cur指向单链表的头节点。

3. 遍历链表，每次迭代，将cur指向的节点的next指针指向pre，然后依次将pre、cur、next往后移动一个节点。

4. 当遍历完成后，将单链表的头节点指向pre，即可完成原地逆置。

代码实现如下：```struct ListNode* reverseList(struct ListNode* head){ struct ListNode* pre = NULL;struct ListNode* cur = head;struct ListNode* next = NULL;while(cur != NULL){next = cur->next;cur->next = pre;pre = cur;cur = next;}head = pre;return head;}```需要注意的是，在实现原地逆置时，需要特别注意链表中间节点的next指针指向前一个节点后，后续节点的next指针会断开。

因此，在移动指针时需要先记录下一个节点的位置，避免指针错误。

原地逆置是一种高效的单链表逆置算法，其时间复杂度为O(n)，空间复杂度为O(1)。

在实际应用中，可以使用该算法实现链表的逆置操作。

单链表就地逆置算法摘要：1.单链表概述2.单链表就地逆置算法的思路3.单链表就地逆置算法的实现4.单链表就地逆置算法的优点与应用场景正文：一、单链表概述单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含两个部分：数据域和指针域。

数据域用于存储数据，指针域则用于存储下一个节点的地址。

单链表只有一个头节点，但没有尾节点。

在单链表中，我们可以通过遍历指针域来访问整个链表中的数据。

二、单链表就地逆置算法的思路单链表就地逆置算法是一种在原地对单链表进行逆置的操作。

它的主要思路是：从链表的头节点开始，遍历整个链表，同时将当前节点的指针域指向下一个节点，然后将下一个节点的数据域与当前节点的数据域进行交换。

这样，在遍历完整个链表后，链表的头节点将变为尾节点，尾节点将变为头节点，从而实现了链表的逆置。

三、单链表就地逆置算法的实现以下是单链表就地逆置算法的实现过程：1.定义一个指向链表头节点的指针pre，初始时pre 指向头节点。

2.定义一个指向链表尾节点的指针p，初始时p 指向头节点。

3.使用while 循环，当pre 不为空时进行以下操作：a.将p 指向的节点的数据域与pre 指向的节点的数据域进行交换。

b.将pre 指向下一个节点，即pre = pre->next。

c.将p 指向下一个节点，即p = p->next。

4.循环结束后，链表的头节点即为原尾节点，尾节点即为原头节点，实现了链表的逆置。

四、单链表就地逆置算法的优点与应用场景单链表就地逆置算法的优点在于其空间复杂度为O(1)，即只需要常数级别的额外空间。

此外，该算法的时间复杂度也为O(n)，其中n 为链表的长度。

因此，该算法在处理较长的链表时，依然具有较高的效率。

数据结构与算法的课程设计课程设计题目：数据结构的逆置算法院系名称：信息技术学院专业（班级）：计算机2班姓名：学号：指导教师：实验内容：分别用一维数组，单链表，双链表实现逆置（一）使用一维数组实现逆置1.需求分析：定义一个一维数组（整型），用for语句实现循环，给数组元素赋值，并将数组元素逆序输出。

2.详细设计：main(){ int a[3],i; /*定义元素个数为3的一维数组*/for(i=0;i<3;i++)scanf("%d",&a[i]);for(i=2;i>=0;i--)printf("%d ",a[i]);getch();}3.运行及调试：4.附录：#include<stdio.h>void main(){ int a[3],i; /*定义一维数组*/for(i=0;i<3;i++)scanf("%d",&a[i]);for(i=2;i>=0;i--)printf("%d ",a[i]);getch();}（二）单链表实现逆置1.需求分析：创建一个单链表并实现逆序输出2.详细设计：定义的所有数据类型，对每个操作写出伪码算法；对主程序和其他模块也都写出伪码算法。

（1）单链表的定义typedef struct node{ int data;/*数据域为整型*/struct node* next; /*定义结点的指针域*/}LinkList;/*数据结点*/（2）头插法建立单链表Tnode *CreatList(){ Tnode *head; /*头指针*/LinkList *p;/*工作指针/int ip;head=(Tnode *)malloc(sizeof(Tnode));head->next=NULL;/*链表开始为空*/printf("please input the number:\n");scanf("%d",&ip); /*向链表中添加元素*/while(ip!=000){ p=(LinkList *)malloc(sizeof(LinkList));/*生成新结点*/ p->data=ip; /*将值赋给新生结点*/p->next=head->next;head->next=p;scanf("%d",&ip);}if(ip==000) /*当输入的数值为000时结束*/printf("\nthe ip is end!\n\n");return head;}（3）读取链表中的数据void ReadList(Tnode *head){ LinkList *p;p=head->next;while(p){ printf("%d ",p->data);p=p->next;}printf("\n");}（4）链表的倒置void ExchangeList(Tnode *head){ LinkList *r,*s;r=head->next;head->next=NULL;while(r){ s=r->next;r->next=head->next;head->next=r;r=s;}3.运行及调试5.附录：/*带头结点的链表建立*/#include<stdio.h>#include<malloc.h>#include<conio.h>typedef struct node /*结点类型定义*/{ int data; /*结点的数据域*/struct node* next; /*结点的指针域*/}LinkList;/*数据结点*/typedef struct{ int length; /**链表的长度/struct node*next; /*结点的指针域*/}Tnode; /*头结点*/Tnode *CreatList()/*头插法建立单链表*/{ Tnode *head;LinkList *p;/*工作指针*/int ip;head=(Tnode *)malloc(sizeof(Tnode));head->next=NULL; /*链表开始为空*/printf("please ip the number:\n");scanf("%d",&ip);while(ip!=000){ p=(LinkList *)malloc(sizeof(LinkList)); /*生成新结点*/ p->data=ip; /*将元素值赋给新生结点p*/p->next=head->next;head->next=p; /*head指向p结点*/scanf("%d",&ip);if(ip==000)printf("\nthe ip is end!\n\n");return head;}void ReadList(Tnode *head) /*读取链表中的数据*/{ LinkList *p;p=head->next;while(p){printf("%d ",p->data);p=p->next;}printf("\n");}void ExchangeList(Tnode *head) /*链表的倒置*/{ LinkList *r,*s;r=head->next;head->next=NULL;while(r){ s=r->next;r->next=head->next;head->next=r;r=s;}}void Readme(){ printf("press 1 to set libiao\n");printf("press 0 to exit\n");printf("-------------------------------------------------------------------------------\n"); }void main(){ Tnode *head;int choice;while(choice){ Readme();scanf("%d",&choice);switch(choice){ case 1:head=CreatList(); /*创建单链表*/printf("the number are:\n\n");ReadList(head);printf("\n");ExchangeList(head); /**逆置后的单链表/printf("the exchange number are:\n\n"); /*打印逆置后的单链表*/ReadList(head); /*读取单链表中的数据*/getch();break;}}}（三）双链表实现逆置1.需求分析：创建一个双链表并实现逆序输出2.详细设计：定义的所有数据类型，对每个操作写出伪码算法；对主程序和其他模块也都写出伪码算法。

单链表逆置原理
单链表逆置原理是通过改变链表中节点的指向，将链表中的节点重新排列，使得原来链表的顺序颠倒过来。

具体实现方法是使用三个指针，一个指向当前节点，一个指向上一个节点，一个指向下一个节点。

通过交换当前节点的下一个节点和上一个节点的下一个节点，实现节点的逆置。

在每一轮循环中，用p3记录p2的next位置，将p2的next指向p1，最后让p1指向p2，p2指向p3。

整个循环结束以后，p2停留在原来链表尾部的NULL处，p1停留在原来链表的最后一个元素。

其特点包括：
1.改变原链表的顺序：通过逆置操作，可以将单链表的顺序完全颠倒，变
为反向的顺序。

2.操作简单：相对于其他数据结构，单链表的逆置操作相对简单，只需要
遍历链表并交换相邻节点的指向即可。

3.对原链表无影响：逆置操作不会改变原链表中节点的值，只是改变了它
们的指向，因此不会对原链表造成任何影响。

4.适用于需要反向存储的数据结构：单链表的逆置操作可以用于需要反向
存储的数据结构，如某些算法或数据压缩等应用中。

需要注意的是，单链表的逆置操作需要小心处理边界条件和错误情况，例如链表为空或只有一个节点等情况。

同时，在逆置操作过程中需要注意内存管理，避免出现内存泄漏等问题。

逆置单链表（基于c语⾔）直接插⼊全部代码：（reverseLinklist函数是逆置操作）#include <stdio.h>#include <stdlib.h>#include <assert.h>typedef int LDataType;typedef struct Linklist{LDataType data;struct Linklist *next;}Linklist,*pLinklist;pLinklist BuyNewNode(LDataType data); //动态⽣成新结点void InitLinklist(pLinklist *pL); //初始化单链表void PushBackLinklist(pLinklist *pL,LDataType data); //尾插void PushFrontLinklist(pLinklist *pL,LDataType data); //头插void PopBackLinklist(pLinklist* pL); //尾删void PopFrontLinklist(pLinklist *pL); //头删void PrintLinklist(Linklist *pL); //打印单链表pLinklist FindLinklist(pLinklist *pL,LDataType data); //查找指定元素，返回元素位置void InsertLinklist(pLinklist *pL,pLinklist p,LDataType data); //指定位置插⼊void RemoveLinklist(pLinklist* pL,LDataType data); //删除第⼀个指定元素void RemoveAllLinklist(pLinklist *pL,LDataType data); //删除所有指定元素int IsEmptyLinklist(pLinklist pL); //判断链表是否为空void DestoryLinklist(pLinklist *pL); //销毁单链表pLinklist reverseLinklist(pLinklist *pL);int main(void){Linklist *first = NULL;InitLinklist(&first);PushBackLinklist(&first,5);PushBackLinklist(&first,4);PushBackLinklist(&first,3);PushBackLinklist(&first,2);PushBackLinklist(&first,1);PushBackLinklist(&first,0);PushFrontLinklist(&first,6);first = reverseLinklist(&first);PushFrontLinklist(&first,-1);PrintLinklist(first);}pLinklist BuyNewNode(LDataType data){pLinklist NewNode = (pLinklist)malloc(sizeof(Linklist));if (NewNode == NULL){printf("动态开辟内存空间失败\n");return NULL;}NewNode->data = data;NewNode->next = NULL;return NewNode;}void InitLinklist(pLinklist *pL){assert(pL != NULL); //初始化操作(*pL) = NULL;}void PushBackLinklist(pLinklist *pL,LDataType data){assert(pL != NULL); //尾插⼀个数据域为data的结点pLinklist NewNode = BuyNewNode(data);if(*pL == NULL){*pL = NewNode;return ;}pLinklist cur = *pL;while(cur->next){cur = cur->next;}cur->next = NewNode;}void PushFrontLinklist(pLinklist *pL,LDataType data){assert(pL != NULL); //头插⼀个数据域为data的结点pLinklist NewNode = BuyNewNode(data);if(*pL == NULL){*pL = NewNode;return ;}NewNode->next = *pL;*pL = NewNode;}int IsEmptyLinklist(pLinklist pL){return (pL == NULL); //判断⽆头单链表是否为空}void PopBackLinklist(pLinklist *pL){assert(pL != NULL); //尾删if(IsEmptyLinklist(*pL)){puts("链表为空，删除失败");return ;}pLinklist cur = *pL;pLinklist pre;if(cur->next == NULL){//只有⼀个结点*pL = NULL;free(cur);cur = NULL;return ;}while(cur->next){pre = cur;cur = cur->next;}pre->next = NULL;free(cur);cur = NULL;}void PopFrontLinklist(pLinklist *pL){assert(pL != NULL); //头删，既是删除第⼀个结点if(*pL == NULL){printf(" 链表为空，删除失败");return ;}pLinklist cur = *pL;*pL = cur->next;free(cur);cur = NULL;}pLinklist FindLinklist(pLinklist *pL,LDataType data){assert( pL != NULL); //找到第⼀个数据为data的结点pLinklist cur = *pL;while(cur){if (cur->data == data){return cur;}cur = cur->next;}return NULL;}void InsertLinklist(pLinklist *pL,pLinklist p,LDataType data){assert(pL != NULL); //xiangp结点之前插⼊⼀个数据为data的元素 pLinklist NewNode = BuyNewNode(data);pLinklist cur = *pL;while(cur->next != p){cur = cur->next;}NewNode->next = p;cur->next = NewNode;}void RemoveLinklist(pLinklist *pL,LDataType data){assert(pL != NULL); //删除第⼀个数据域为data的结点pLinklist cur = NULL;pLinklist p = *pL;pLinklist pre = NULL;cur = FindLinklist(pL,data);if (cur == NULL){printf("未找到要删除的元素");return ;}if (*pL == cur){//位于第⼀个结点*pL = cur->next;free(cur);cur = NULL;return ;}while(p != cur){pre = p;p = p->next;}pre->next = cur->next;free(cur);cur = NULL;}void RemoveAllLinklist(pLinklist *pL,LDataType data){assert(pL != NULL); //删除每⼀个数据域都是data的结点pLinklist cur = NULL;pLinklist p = *pL;pLinklist pre = *pL;while(p){if (p->data == data && (*pL) == p){//第⼀个结点是pre = p;p = p->next;*pL = p;free(pre);pre = NULL;}else if(p->data == data){//后续结点是cur = p;p = p->next;pre->next = p;free(cur);cur = NULL;}else{//此结点不是pre = p;p = p->next;}}}void PrintLinklist(Linklist *pL){pLinklist cur = pL; //打印链表while(cur){printf("%d--->",cur->data);cur = cur->next;}printf("NULL\n");}void DestoryLinklist(pLinklist *pL){assert(pL != NULL); //摧毁链表pLinklist cur = *pL;pLinklist pre = NULL;if (*pL == NULL){printf("链表为空");return ;}if (cur->next = NULL){*pL = NULL;free(cur);cur = NULL;return ;}while(cur){pre = cur;cur = cur->next;free(pre);pre = NULL;}}pLinklist reverseLinklist(pLinklist *pL){if((*pL) == NULL || pL == NULL){return NULL;}if((*pL)->next == NULL){return *pL;}Linklist *p = *pL;Linklist *q = (*pL)->next;Linklist *r = *pL;while(q->next != NULL){r = q->next;q->next = p；p = q;q = r;r = r->next;}q->next = p;(*pL)->next = NULL;*pL = q;return *pL;}第⼀步就是判断这个单链表是否为空，因为我⽤了⼆级指针，因此要看链表为空的同时还要看pL是否指向有问题。

单链表的逆置单链表的逆置是⾯试官⾮常青睐的题，这个题可以看出⾯试者对链表和指针的操作。

⽽且问题也很好描述，⼀句话就表达出了⾃⼰的题。

----------------------------------------------------------------------------------------------⼀、算法思想：（头插法）<1>,将源链表分为链表头和链表实体。

<2>,将链表实体节点⽤头插法依次插⼊到链表头中。

<3>,如果链表实体插完则算法结束，否则转到<2>.--------------------------------------------------------------------------------------------⼆、算法的实现：头插法：void reverse(struct node *head){if (head == NULL)return ;struct node *p = head->next,*pnext = NULL;head->next = NULL;while (p != NULL) {pnext = p->next;p->next = head->next;head->next = p;p = pnext;}return ;}利⽤辅助指针void ListReverse2(LinkList L){LNode *real = L->next; //带头结点的链表，real指向第⼀个实结点//real为NULL，则链表为只含头结点的空表//real->nexxt为NULL，则链表只含有⼀个结点if(real == NULL || real->next == NULL)return;LNode *pre = real; //先前指针LNode *cur = real->next; //当前指针LNode *suc = NULL; //后继指针while(cur != NULL){suc = cur->next;cur->next = pre;pre = cur;cur = suc;}real->next = NULL; //while执⾏后第⼀个结点和第⼆个结点互指L->next = pre; //记录新的头结点}。