双向链表的逆置

ｃ语⾔链表逆序的问题去⾯试被问到⼀个问题，怎么把⼀个链表反转(⽤原链表)，⾃⼰在⽹上找了到了⼀篇⽂章，/sicofield/article/details/8850269，原作者给出了三种⽅法，⽅法⼀：将链表数据全部读到数组中，然后在倒序输出。

⽅法⼆：就是我下⾯要讲的。

⽅法三：从第⼆个结点开始，把之后的每个结点都插⼊到第⼀个结点之后，最后在把第⼀个结点挪到表尾。

第⼆种⽅法的思路是：从第⼆个结点开始，记录它的下个结点，把它挪到第⼀个结点之前，成为新表头，然后下个结点继续这个过程。

1struct stu *reserve(struct stu *head)2 {3struct stu *p1,*p2,*p3; 4 p1=head;5 p2=p1->next; //　这个结点为要移动的结点6while(p2)7 {8 p3=p2->next; //记录的为要移动的结点的下⼀个结点9 p2->next=p1; //移动结点到最前10 p1=p2; //移动的结点变为新表头11 p2=p3; //下个结点变为要移动的结点12 }13 head->next=NULL; //移动完毕后head变为表尾，让它指向为空14 head=p1; 15return head;16 }⽅法三的贴下原作者的代码加上⾃⼰的思路：1struct stu *reserve(struct stu *head)2 {3struct stu *p,*q;4 p=head->next; //记录第⼆个结点5while(p->next!=NULL)6 {7 q=p->next; //记录要移动的结点8 p->next=q->next; //把该结点从原链表中移除9 q->next=head->next; //把该结点连接到head之后10 head->next=q;11 }12 p->next=head; //把head移动到新表尾，此时链表成环13 head=p->next->next; //找到移动完之后的新head14 p->next->next=NULL; //断开环15return head;1617 }。

首先，双向链表中每个结点有两个指针域，一指后继，一指前趋。

在当前结点b(指针为p)前插入新结点x(指针为s)时，(当前结点的前趋指向为结点a），其目的是将链表的顺序由a<-->b变为a<-->x<-->b。

书中的四步是：1. 1. s->prior = p->prior; //将当前结点b的前趋赋给新结点x的前趋，即让结点x的前趋指向结点a2.3. 2. p->prior->next = s; //将结点b的前趋的后继指向结点x，即让结点a的后继指向结点x，实现a<-->x互联4.5. 3. s->next = p; //将结点x的后继指向结点b6.7. 4. p->prior =s; //将结点b的前趋指向结点x，实现x<-->b互联复制代码上面这四步在不做改动的情况下，1和2顺序可互换，3和4顺序可互换，但3、4整体不能和1、2整体顺序互换，因为这是在当前结点前插入结点，所以必须先将其前趋a与x互联起来，否则，若先将x<-->b互联起来，就无法访问到结点a，无法来进行a<-->x的互联了。

在当前结点b后插入新结点x道理和这个基本上是一样的，不同点就是要先将当前结点的后继(假定为结点c)和新结点x互联，然后再将当前结点b和新结点x互联。

四步应为：1. 1. s->next = p.next; //让结点x的后继指向结点c2.3. 2. p->next->prior = s; //让结点c的前趋指向结点x，实现x<-->c互联4.5. 3. s->prior = p; //让结点x的前趋指向结点b6.7. 4. p->next = s; //让结点b的后继指向结点x，实现b<-->x互联复制代码这样就实现了由b<-->c变成了b<-->x<-->c。

《数据结构》复习题一．选择题：1．数据结构是研究数据的( ) 以及它们之间的相互关系A．理想结构，物理结构B．理想结构，抽象结构C．物理结构，逻辑结构D．抽象结构，逻辑结构2. 组成数据的基本单位是（）A.数据项B.数据类型C. 数据元素D. 数据变量3. 如果某数据结构的数据元素的集合为S={A,B,C,D,E,F,G}，元素之间的关系为R={<A,D>,<A,G>,<D,B>,<D,C>,<G,E>,<G,F>},则该数据结构是一种（）A.线性结构B. 树结构C. 图结构D. 链表结构4. 线性表的链接实现有利于( ) 运算A.插入B.读表元C.查找D.定位5. 设一数列的输入顺序为1，2，3，4，5，6通过栈操作不可能排成的输出序列为（）A. 3，2，5，6，4，1B. 1，5，4，6，2，3C. 2，4，3，5，1，6D. 4，5，3，6，2，16. 设字符串S1=‘ABCDEFG’，S2=‘PQRST’则运算S=Concat(Sub(S1,2,Length(S2)),Sub(S1,Length(S2),2))后结果为（）A.‘BCQR’B.‘BCDEF’C.‘BCDEFG’D.‘BCDEFEF’7. 设单链表中指针P指向结点A，若要删除A之后的结点（若存在），则修改指针的操作为（）A. p→next= p→next→nextB. p= p→nextC. p= p→next→nextD. p→next = p8. 线性表采用链式存储时，其地址（）A. 必须是连续的B.部分地址必须是连续的C. 一定是不连续的D.连续与否均可以9. 在内部排序时，排序不稳定的有（）A.插入排序B. 冒泡排序C. 快速排序D.归并排序10. 设有1000个元素，用折半法查找时，最小比较次数为（）A.0B. 1C.10D. 50011. 将一个元素进入队列的时间复杂度是（）n)A. O (1)B. O (n)C. O (n2)D. O (log212. 在一个具有n个结点的单链表中查找其值等x的结点，在查找成功的情况下，需要比较（）个元素结点A. n/2B. nC. (n+1)/2D. (n-1)/213. 从一个长度为n的顺序表中删除第i个元素(1≤i≤n)，需向前移动（）个元素A. n-iB. n-i+1C. n-i-1D. i14. 总共3层的完全二叉树，其结点数至少有（）A.3B. 4C.7D.815. 队列操作的原则是（）A. 先进先出B.后进先出C. 只能进行插入D. 只能进行删除16. 若线性表最常用的操作是存取第i个元素及其前驱元素的值，则采用（）存储方式最节省时间A.单链表B. 双向链表C. 音循环链表D. 顺序表17. 栈和队列都是（）A. 顺序存储的线性结构B. 限制存取点的线性结构C. 链接存储的线性结构D. 限制存取点的非线性结构18. 与线性表的链接存储相符的特性是（）A.插入和删除操作灵活B. 需要连续存储空间C. 便于随机访问D. 存储密度大19.若进队序列为1,2,3,则出队序列是（）A.3，2，1B. 1，3，2C. 1，2，3D. 3，2，120. 在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是（）A. p= NULLB. p→next= NULLC. p=hD. p→next= h3. 在双向循环链表中,在指针P所指的结点之后插入指针f所指的结点,其操作为。

双链表反向的7种方法
双链表是一种链表数据结构，每个节点除了包含指向下一个节点的指针外，还包含指向前一个节点的指针。

反向双链表意味着将链表中的元素顺序颠倒。

以下是7种常见的反向双链表的方法：
1. 迭代反转，这是最直接的方法，通过遍历双链表并逐个调整节点的前后指针指向来实现反转。

2. 递归反转，使用递归函数来反转双链表，递归函数在每一层递归中反转相邻节点的指针。

3. 栈的方法，使用栈数据结构，将双链表中的节点依次入栈，然后依次出栈，构建一个新的反向双链表。

4. 头插法，遍历原始双链表，将每个节点插入到一个新的空双链表的头部，这样就能得到反向的双链表。

5. 尾插法，类似于头插法，不同的是将每个节点插入到新双链表的尾部，最后得到反向的双链表。

6. 逆序遍历，先正向遍历双链表，将节点值存储在一个数组中，然后逆序遍历数组，将值依次赋给新的双链表节点，得到反向的双
链表。

7. 交换节点值，遍历双链表，将第一个节点和最后一个节点的
值交换，然后将第二个节点和倒数第二个节点的值交换，以此类推，直到遍历到中间节点为止，这样就能得到反向的双链表。

以上是7种常见的反向双链表的方法，每种方法都有其适用的
场景和实现的复杂度，在实际应用中可以根据具体情况选择合适的
方法来实现双链表的反向操作。

标题：C语言编程ACM：链表的逆置一、概述ACM（Advanced Computing Machinery）竞赛是计算机科学领域最负盛名的竞赛之一，要在ACM竞赛中获得优异的成绩，熟练掌握C 语言编程技术是必不可少的。

本文将讨论C语言编程中常见的ACM题目之一：链表的逆置。

二、链表的基本概念1.链表的定义链表是一种线性表的物理存储单位，由一个个节点组成，每个节点包含数据元素和下一个节点的指针。

链表中的数据元素可以是任意类型。

2.链表的基本操作在C语言中，链表的基本操作包括插入节点、删除节点、查找节点等。

而链表的逆置就是将链表中的节点顺序颠倒。

三、链表的逆置方法在C语言中，链表的逆置可以采用多种方法实现。

1.迭代法迭代法是最直接的方法，具体步骤如下：（1）初始化三个指针，分别指向当前节点、前一节点、后一节点。

（2）遍历链表，将当前节点的指针指向前一节点。

（3）更新前一节点和当前节点的位置。

（4）遍历结束后，前一节点指向NULL，表示逆置完成。

2.递归法递归法是一种更为巧妙的方法，具体步骤如下：（1）递归遍历链表，直至到达链表尾部。

（2）从链表尾部开始，逐一修改每个节点的指针指向。

（3）递归结束后，链表即被逆置。

四、链表逆置的C语言实现以下是链表逆置的C语言实现代码，以迭代法为例：```ctypedef struct Node {int data;struct Node* next;} Node;Node* reverseList(Node* head) {Node *prev = NULL, *curr = head, *next = NULL; while (curr) {next = curr->next;curr->next = prev;prev = curr;curr = next;}return prev;}```五、实例分析假设有一个链表的头指针为head，包含数据元素1、2、3、4、5。

双向链表逆序双向链表的逆序操作可以通过修改节点之间的引用关系来实现。

具体步骤如下：1. 定义三个指针：pre表示当前节点的前一个节点，cur表示当前节点，next表示当前节点的后一个节点；2. 遍历整个链表，初始时将pre设置为null，cur设置为链表的头节点；3. 在遍历过程中，先将next指向cur的后一个节点；4. 将cur的next指向pre，将cur的prev指向next。

5. 更新pre和cur，将cur指向next，pre指向cur；6. 重复步骤3~5，直到遍历到链表的最后一个节点。

7. 将最后一个节点的prev指向null，表示链表逆序完成。

以下是Java代码示例：```public class DoublyLinkedList {Node head;class Node {int data;Node prev;Node next;Node(int d) {data = d;prev = null;next = null;}}public void reverse() {Node temp = null;Node current = head;while (current != null) {temp = current.prev;current.prev = current.next;current.next = temp;current = current.prev;}if (temp != null) {head = temp.prev;}}}```注意：逆序之后，原来的头结点会变成尾结点，原来的尾结点会变成头结点。

第8讲 双向链表● 循环单链表的出现，虽然能够实现从任一结点出发沿着链能找到其前趋结点，但时间耗费是O (n) 。

● 如果希望从表中快速确定某一个结点的前趋，另一个解决方法就是在单链表的每个结点里再增加一个指向其前趋的指针域prior 。

这样形成的链表中就有两条方向不同的链，我们称之为双向链表。

● 双向链表的结构定义如下：typedef struct DNode{ ElemType data ；struct DNode *prior ，*next ；}DNode, * DoubleList ；● 双向链表的结点结构如图所示。

图：双链表的结点结构注：● 双向链表也是由头指针唯一确定的，● 增加头结点能使双链表的某些运算变得方便● 由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。

● 设指针p 指向双链表中某一结点，则有下式成立：p->prior->next = p = p->next->prior●在双向链表中，那些只涉及后继指针的算法，如求表长度、取元素、元素定位等，与单链表中相应的算法相同，● 但对于前插和删除操作则涉及到前驱和后继两个方向的指针变化，因此与单链表中的算法不同。

1、 双向链表的前插操作【算法思想】欲在双向链表第i 个结点之前插入一个的新的结点，则指针的变化情况如图所示：… p …s->prior=p->prior; ①p->prior->next=s;②s->next=p; ③p->prior=s;④【算法描述】int DlinkIns(DoubleList L,int i,ElemType e){DNode *s,*p;… /*先检查待插入的位置i是否合法（实现方法同单链表的前插操作）*/… /*若位置i合法，则找到第i个结点并让指针p指向它*/s=(DNode*)malloc(sizeof(DNode));if (s){ s->data=e;s->prior=p->prior; ①p->prior->next=s; ②s->next=p; ③p->prior=s; ④r eturn TRUE;}else return FALSE;}2、双向链表的删除操作【算法思想】欲删除双向链表中的第i个结点，则指针的变化情况如图所示：p->prior->next=p->next; ①p->next->prior=p->prior; ②free(p);【算法描述】int DlinkDel(DoubleList L,int i,ElemType *e){DNode *p;… /*先检查待插入的位置i 是否合法（实现方法同单链表的删除操作）*/… /*若位置i 合法，则找到第i 个结点并让指针p 指向它*/*e=p->data;p->prior->next=p->next; ①p->next->prior=p->prior; ②free(p);return TRUE;}3、 双向循环链表双向链表可以有循环表,称为双向循环链表。

数据结构与算法的课程设计课程设计题目：数据结构的逆置算法院系名称：信息技术学院专业（班级）：计算机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.详细设计：定义的所有数据类型，对每个操作写出伪码算法；对主程序和其他模块也都写出伪码算法。

链表逆置算法链表是一种常用的数据结构，它由一系列的节点组成，每个节点包含一个数据元素和一个指针，用于指向下一个节点。

在实际应用中，经常需要将链表进行逆置操作，即将链表中的元素反序排列。

本文将介绍链表逆置算法的实现原理和具体步骤。

链表逆置算法的实现原理是通过改变节点之间的指针指向关系，将原来的链表转换为一个逆序的链表。

具体步骤如下：1. 定义三个指针：prev、cur和next。

其中prev用于指向当前节点的前一个节点，cur用于指向当前节点，next用于保存当前节点的下一个节点。

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

3. 在循环中，依次对cur指针指向的节点进行操作，直到cur指向链表的最后一个节点。

循环条件可设为cur不为空。

4. 在循环中，将next指针指向cur的下一个节点。

5. 将cur的指针指向prev，实现节点指针的反向。

6. 将prev指针指向cur，cur指针指向next。

7. 遍历完所有节点后，将链表的头节点指向prev，即可得到逆序的链表。

下面通过一个具体例子来说明链表逆置算法的实现过程：假设有一个链表，包含5个节点，数据分别为1、2、3、4、5。

初始状态下，链表的指针指向关系如下：1 ->2 ->3 ->4 -> 5按照上述步骤进行逆置操作：1. 初始化prev、cur和next指针。

2. cur指向链表的头节点，即1。

3. 在循环中，将next指向cur的下一个节点，即2。

4. 将cur的指针指向prev，实现节点指针的反向，此时第一个节点指向null。

5. 将prev指向cur，cur指向next。

6. 继续循环，next指向cur的下一个节点，即3。

7. 将cur的指针指向prev，实现节点指针的反向，此时第二个节点指向第一个节点。

8. 将prev指向cur，cur指向next。

9. 继续循环，重复上述步骤，直到遍历完所有节点。

最终得到的逆序链表的指针指向关系如下：5 -> 4 -> 3 -> 2 -> 1通过链表逆置算法，我们可以将链表中的元素反序排列，实现了链表的逆置操作。

链表逆序的三种方法链表是一种常用的数据结构，由一个个节点通过指针连接而成。

在实际编程中，经常需要对链表进行逆序操作，以满足特定需求。

本文将介绍链表逆序的三种常用方法，分别是迭代法、递归法以及使用栈的方法。

迭代法：迭代法是一种比较直观的逆序方法，通过调整节点之间的指针指向来实现。

具体步骤如下：1. 定义三个指针，分别为当前节点（cur）、前一个节点（prev）和下一个节点（next）。

2. 将当前节点的下一个节点保存到next指针中，以免链表断开。

3. 将当前节点的next指针指向前一个节点，完成逆序操作。

4. 将当前节点赋值给prev指针，以备下一次迭代使用。

5. 将next指针赋值给cur指针，继续下一次迭代。

若next指针为空，则说明已到达链表尾部，逆序完成。

递归法：递归法是一种更为简洁的逆序方法，通过递归调用实现链表逆序。

具体步骤如下：1. 首先判断链表是否为空或只有一个节点，若是则无需逆序，直接返回。

2. 若链表有多个节点，则递归调用逆序函数对除第一个节点外的子链表进行逆序。

3. 将头节点（首节点）的指针指向调用逆序函数后的新链表的尾节点。

4. 将尾节点的指针指向头节点，使得整个链表逆序完成。

使用栈的方法：栈是一种后进先出（LIFO）的数据结构，可以利用栈的特性进行链表逆序操作。

具体步骤如下：1. 遍历链表，将链表中的节点依次压入栈中。

2. 弹出栈中的节点，按照出栈顺序重新构建链表。

弹出的第一个节点是原链表的尾节点，成为逆序链表的头节点。

3. 将每个弹出的节点的next指针指向下一个被弹出的节点，完成逆序操作。

4. 最后一个被弹出的节点成为逆序链表的尾节点，将其next指针置为空，表示逆序链表的尾部。

以上是三种常见的链表逆序方法。

在实际应用中，可以根据具体情况选择合适的方法来实现链表逆序。

迭代法适合逆序链表并保持链表结构的情况；递归法适用于逆序链表不要求保持原结构的情况；使用栈的方法适用于逆序链表并重新构建链表结构的情况。