数据结构单链表、双链表的逆置算法

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

⼀个链表，奇数位升序偶数位降序，让链表变成升序的题⽬描述：⼀个链表，奇数位升序偶数位降序，让链表变成升序的。

⽐如：1 8 3 6 5 4 7 2 9，最后输出1 2 3 4 5 6 7 8 9。

分析：这道题可以分成三步：⾸先根据奇数位和偶数位拆分成两个链表。

然后对偶数链表进⾏反转。

最后将两个有序链表进⾏合并。

package com.test;public class Main {public static void main(String[] args) {Main main = new Main();ListNode head = main.initList();main.printList(head);ListNode[] heads = main.splitList(head);main.printList(heads[0]);main.printList(heads[1]);ListNode reverseHead = main.reverseList(heads[1]);main.printList(reverseHead);ListNode mergeHead = main.mergeLists(heads[0], reverseHead);main.printList(mergeHead);}//按照奇偶位拆分成两个链表private ListNode[] splitList(ListNode head) {ListNode head1 = null;ListNode head2 = null;ListNode cur1 = null;ListNode cur2 = null;int count = 1;while (head != null) {if (count % 2 == 1) {if (cur1 != null) {cur1.next = head;cur1 = cur1.next;} else {cur1 = head;head1 = cur1;}} else {if (cur2 != null) {cur2.next = head;cur2 = cur2.next;} else {cur2 = head;head2 = cur2;}}head = head.next;++count;}//跳出循环，要让最后两个末尾元素的下⼀个都指向nullcur1.next = null;cur2.next = null;ListNode[] heads = new ListNode[]{head1, head2};return heads;}//反转链表private ListNode reverseList(ListNode head) {ListNode cur = head;ListNode pre = null;ListNode next = null;while (cur != null) {next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}//合并两个有序链表private ListNode mergeLists(ListNode head1, ListNode head2) {if (head1 == null && head2 == null) {return null;}if (head1 == null || head2 == null) {return head1 == null ? head2 : head1; }ListNode first = new ListNode(-1);ListNode cur = first;while (head1 != null && head2 != null) { if (head1.val < head2.val) {cur.next = head1;head1 = head1.next;} else {cur.next = head2;head2 = head2.next;}cur = cur.next;}cur.next = head1 != null ? head1 : head2; return first.next;}//初始化链表private ListNode initList() {ListNode node1 = new ListNode(1);ListNode node2 = new ListNode(8);ListNode node3 = new ListNode(3);ListNode node4 = new ListNode(6);ListNode node5 = new ListNode(5);ListNode node6 = new ListNode(4);ListNode node7 = new ListNode(7);ListNode node8 = new ListNode(2);ListNode node9 = new ListNode(9);node1.next = node2;node2.next = node3;node3.next = node4;node4.next = node5;node5.next = node6;node6.next = node7;node7.next = node8;node8.next = node9;return node1;}//打印链表private void printList(ListNode head) {if (head == null) {return;}ListNode cur = head;while (cur.next != null) {System.out.print(cur.val + "\t");cur = cur.next;}System.out.println(cur.val);}}class ListNode {public int val;public ListNode next;public ListNode() {}public ListNode(int val) {this.val = val;this.next = null;}}。

双链表反向的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。

第 2 章线性表课后习题讲解1. 填空⑴在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。

【解答】表长的一半，表长，该元素在表中的位置⑵顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。

【解答】108【分析】第5个元素的存储地址=第1个元素的存储地址＋(5－1)×2=108⑶设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。

【解答】p->next=(p->next)->next⑷单链表中设置头结点的作用是（）。

【解答】为了运算方便【分析】例如在插入和删除操作时不必对表头的情况进行特殊处理。

⑸非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。

【解答】p->next=head【分析】如图2-8所示。

⑹在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。

【解答】s->next =rear->next; rear->next =s; rear =s;q=rear->next->next; rear->next->next=q->next; delete q;【分析】操作示意图如图2-9所示：⑺一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。

【解答】Ο(1)，Ο(n)【分析】在p所指结点后插入一个新结点只需修改指针，所以时间复杂度为Ο(1)；而在给定值为x的结点后插入一个新结点需要先查找值为x的结点，所以时间复杂度为Ο(n)。

⑻可由一个尾指针唯一确定的链表有（）、（）、（）。

【解答】循环链表，循环双链表，双链表2. 选择题⑴线性表的顺序存储结构是一种（）的存储结构，线性表的链接存储结构是一种（）的存储结构。

数据结构与算法的课程设计课程设计题目：数据结构的逆置算法院系名称：信息技术学院专业（班级）：计算机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. 定义三个指针：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通过链表逆置算法，我们可以将链表中的元素反序排列，实现了链表的逆置操作。