倒置单链表的算法

单链表的逆置（头插法，就地逆转）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;
}。

编写算法：实现带头结点单链表的逆置算法介绍本文将介绍如何编写算法来实现带头结点单链表的逆置操作。

逆置操作是将链表的元素顺序颠倒，即原链表的最后一个节点变为头节点，倒数第二个节点变为第二个节点，以此类推。

实现这个算法需要通过修改指针的指向来完成。

算法实现思路逆置链表的常用方法是使用三个指针prev、current和next： 1. prev指向前一个节点，current指向当前节点，next指向下一个节点。

2. 首先将current节点的下一个节点保存在next指针中，然后将current节点的next指针指向prev节点，实现反转。

3. 接着将prev指针指向current节点，current指针指向next 节点，实现对链表的遍历。

4. 重复上述步骤直到遍历完整个链表，最后将头节点的next指针指向prev节点，完成链表逆置。

伪代码prev = nullcurrent = head.nextwhile(current != null) {next = current.nextcurrent.next = prevprev = currentcurrent = next}head.next = prev算法实现步骤解析初始化1.将prev的初始值设为null，因为头节点的前一个节点不存在。

2.将current的初始值设为头节点的下一个节点，即链表中的第一个节点。

遍历链表1.进入循环，判断current节点是否为null。

如果为null，则表示已经遍历完整个链表。

2.在循环中，首先将current节点的下一个节点保存在next指针中，因为链表逆置的过程中会改变节点的next指向。

3.然后将current节点的next指针指向prev节点，实现反转操作。

4.接着将prev指针指向current节点，即将prev指向已经逆置的部分链表。

5.最后将current指针指向next节点，即将current指向下一个要遍历的节点。

单链表倒序算法#include <iostream>#include <stdio.h> using namespace std;struct st{int a;st(int i){ a = i; }struct st* next;};void sort(struct st* &head){st* p = 0;//排序后的链表头st* p1 = head;//排序前的链表头st* p2 = p1;//在排序过程中，保存原始链表头for(;p2;){p2 = p1->next;p1->next = p;//以上2步，是将当前节点从链表中取出然后将指针反向指向 p = p1;//将排序好的链表的头，给pp1 = p2;//将p1重新指向链表的首位置}head = p;//让head重新指向排序好的链表头}void print(struct st* p){for(;p;){cout << p->a << endl;p = p->next;}}int main( void ){st* head = new st(0);st* p = head;p->next = new st(1);p = p->next;p->next = new st(2);p = p->next;p->next = new st(3);p = p->next;p->next = 0;print(head);sort(head);cout << "----------------------" << endl;print(head);return 0;}//20070126=====================可能这么说更好理解点：实际上可以看作是2个list.,从原始list的head开始逐个取节点，然后向目的list的头的位置插入。

数据结构与算法的课程设计课程设计题目：数据结构的逆置算法院系名称：信息技术学院专业（班级）：计算机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.适用于需要反向存储的数据结构：单链表的逆置操作可以用于需要反向
存储的数据结构，如某些算法或数据压缩等应用中。

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

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

编写算法：实现带头结点单链表的逆置算法引言单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含两部分：数据域和指针域。

其中，数据域用于存储数据，指针域用于指向下一个节点。

在单链表中，头结点是第一个节点之前的一个特殊节点，它不存储任何数据。

逆置（或反转）单链表是将原始链表中的节点顺序颠倒过来。

例如，给定一个单链表：1 -> 2 -> 3 -> 4 -> nullptr，逆置后的结果为：4 -> 3 -> 2 -> 1 -> nullptr。

本文将介绍如何实现带头结点单链表的逆置算法，并给出相应的C++代码实现。

算法思路要实现带头结点单链表的逆置算法，可以使用迭代或递归两种方法。

迭代方法迭代方法通过遍历原始链表中的每个节点，并修改其指针域来实现逆置。

具体步骤如下：1.如果链表为空或只有一个节点，则直接返回。

2.定义三个指针：prev、curr和next。

–prev指向当前节点的前一个节点（初始时为nullptr）；–curr指向当前节点；–next指向当前节点的下一个节点。

3.进行循环，直到curr指向nullptr为止：–将curr的指针域修改为prev；–将prev指向curr；–将curr指向next；–将next指向下一个节点。

4.修改头结点的指针域为nullptr，将prev作为新的头结点。

递归方法递归方法通过逐层调用函数来实现逆置。

具体步骤如下：1.如果链表为空或只有一个节点，则直接返回。

2.定义一个递归函数reverseList，该函数接收一个参数：当前节点head。

3.递归终止条件：如果当前节点或当前节点的下一个节点为空，则返回当前节点。

4.在递归调用前，先逆置从下一个节点开始的子链表，并将返回结果保存在变量newHead中。

5.将当前节点的下一个节点的指针域修改为当前节点（即将子链表的尾部连接到当前节点）。

6.将当前节点的指针域修改为空（即将当前节点作为新链表的尾部）。

单链表就地逆置算法单链表就地逆置算法是一种将单链表逆序排列的算法，不需要创建新的链表，而是通过修改链表的指针来实现逆置操作。

这种算法的时间复杂度为O(n)，空间复杂度为O(1)。

在进行单链表就地逆置算法之前，我们需要先了解链表的基本概念和结构。

单链表是由节点组成的数据结构，每个节点包含两个部分：数据域和指针域。

数据域用来存储节点的数据，而指针域用来指向下一个节点。

链表的头节点是链表的第一个节点，尾节点的指针域指向NULL。

现在我们来定义一个单链表的数据结构：```ctypedef struct Node{int data;struct Node *next;```接下来，我们将介绍单链表就地逆置算法的具体实现步骤。

步骤一：检查链表是否为空或只有一个节点，如果是，则不需要进行逆置操作，直接返回头节点。

步骤二：定义三个指针变量，分别为prev、current和next。

```cNode *prev = NULL;Node *current = head;Node *next = NULL;```其中，prev用来指向当前节点的前一个节点，current用来指向当前节点，next用来指向当前节点的下一个节点。

步骤三：遍历链表，将每个节点的指针指向它的前一个节点。

具体操作如下：while(current != NULL){next = current->next;current->next = prev;prev = current;current = next;}```将next指向current节点的下一个节点，然后将current节点的指针指向prev，最后将prev指向current，current指向next。

步骤四：将链表的头节点指向逆置后的链表的头节点。

```chead = prev;```步骤五：返回逆置后的链表头节点。

```creturn head;```下面我们来看一下单链表就地逆置算法的完整代码实现：```cNode *reverseLinkedList(Node *head){if(head == NULL || head->next == NULL){return head;}Node *prev = NULL;Node *current = head;Node *next = NULL;while(current != NULL){next = current->next;current->next = prev;prev = current;current = next;}head = prev;return head;}```通过以上步骤，我们可以实现单链表的就地逆置算法。

单链表的逆置（C++实现） 单链表以及逆置是什么就不说了，就简单说⼀下思想：链表的初始状态：具体的⽅法就是将头节点后⾯的节点，依次通过指针指向，插⼊head头节点之后，即可完成逆置过程．　⽰意图(这⾥我写⼀下中间处理流程，因为这样⽐较直观．第⼀次的处理与正常处理雷同)：需要注意的主要有两点：1.　逆置之后的链表的尾部要NULL．在这⾥就是刚开始的时候的pHead->next->next = nullptr，具体可参考实现代码．2.　当curr指向最后⼀个节点时，需要特殊处理⼀下．实现代码：#include <iostream>using namespace std;template <typename T>struct Node{Node(T t){data = t;}T data;Node *next;};template <typename T>class List{public:List(){CreatList();}~List(){Node<T> *start = head;Node<T> *end = start->next;while (end){delete start;start = end;end = end->next;}delete start;}void CreatList(){head = new Node<T>(-100);Node<T> *temp = nullptr;rear = head;for (int i = 0; i < 10; i++){temp = new Node<T>(i);temp->next = nullptr;rear->next = temp;rear = temp;}rear->next = nullptr;}void ReverseList(){Node<T> *curr, *beh;curr = head->next;rear = head->next;beh = curr->next;while (beh){curr->next = head->next;head->next = curr;curr = beh;beh = beh->next;}curr->next = head->next;/*处理`curr`指向最后⼀个节点*/ head->next = curr;/*处理链表的尾部 nullptr */rear->next = nullptr;}void Print(){Node<T> *temp = head->next;while (temp){std::cout << temp->data << " ";temp = temp->next;}std::cout << std::endl;}private:Node<T> *head;Node<T> *rear;};int main(void){List<int> list;list.Print();list.ReverseList();list.Print();}运⾏结果：附录：顺便⽤⼀下valgrind这个内存检测⼯具我们去掉析构函数，并使⽤：valgrind --tool=memcheck --leak-check=full --show-reachable=yes --trace-children=yes ./a.out其中–leak-check=full 指的是完全检查内存泄漏，–show-reachable=yes是显⽰内存泄漏的地点，–trace-children=yes是跟⼊⼦进程。