单链表原地逆置(头插法)

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

单链表头插法代码单链表是一种常见的数据结构，它由多个节点组成，每个节点包括两部分：一个数据存储区和一个指向下一个节点的指针。

插入操作是单链表的基本操作之一，在插入一个节点时，可以采用两种方法：头插法和尾插法。

在本篇文章中，我们将重点讲解单链表的头插法。

头插法是指在单链表的头节点之前插入一个新节点。

这种方法需要先创建一个新节点，并将其指针指向原头节点所指向的节点。

然后再将头节点的指针指向新节点。

相当于是在链表的头部插入新节点。

下面是头插法的代码实现：```struct node {int data;struct node *next;};void insert_node(struct node **head, int value) {struct node *new_node = (struct node*)malloc(sizeof(struct node));new_node->data = value;new_node->next = *head;*head = new_node;}```在上面的代码中，我们首先定义了一个节点结构体node，其中包含一个int类型的数据成员data和一个指向下一个节点的指针成员next。

然后，我们定义一个函数insert_node，这个函数的作用是向单链表中插入新的节点。

其中，head是指向链表头节点的指针，value 是要插入的节点的值。

在insert_node函数体中，我们首先通过malloc函数动态分配内存，创建一个新节点new_node。

然后，将新节点的data成员赋值为value，将新节点的next指针指向原head指针所指向的节点，最后将head指针指向新节点new_node。

这样，新节点就插入到链表的头部了。

总结一下，头插法是单链表中比较常用的一种插入节点的方式，通过这种方法，可以很方便地在链表头部插入新节点。

在实现的过程中需要注意，在创建新节点时要手动分配内存，否则会发生内存错误。

带头结点单链表中数据就地逆置实验3 ：带头结点单链表中数据就地逆置一、实验目的：1. 会定义单链表的结点类型；2. 熟悉对单链表的一些基本操作和具体的函数定义；3. 了解和掌握单链表的调用格式。

二、实验要求：1. 认真阅读和掌握实验内容所给的程序，并上机运行；2. 保存程序运行结果，并结合程序进行分析；3. 尝试自己调试修改程序并试运行。

三、实验内容：编写算法实现带头结点单链表的就地逆置，即利用原带头结点单链表的结点空间把数据元素序列逆置。

四、实验程序：#include#include#includetypedef int datatype;typedef struct snode{datatype data;struct snode*next;}slnode;sllinitiate(slnode**head);linlistsort(slnode*head);int sllinsert(slnode*head,int i,datatype x);int slldelete(slnode*head,int i,datatype x);int sllget(slnode*head,int i,datatype*x);int sllnotempty(slnode*head);linlistsurt(slnode*head);linlistinsert(slnode*head,datatype x);converse(slnode*head);main(void){datatype test[6]={64,6,7,89,12,24};slnode*head,*p;int n=6,i;sllinitiate(&head);for(i=1;i<=n;i++)sllinsert(head,i,test[i-1]);linlistsort(head);linlistinsert(head,25);converse(head);p=head->next;while(p!=NULL){printf("%d",p->data);p=p->next;}}sllinitiate(slnode**head){if((*head=(slnode*)malloc(sizeof(slnode)))==NULL)exit(1); (*head)->next=NULL;}int sllinsert(slnode*head,int i,datatype x){slnode*p,*q;int j;p=head;j=0;while(p!=NULL&&j<i-1)< p="">{p=p->next;j++;}if(j!=i-1){printf("the insert-position parameter is wrong!\n"); return 0;}if((q=(slnode*)malloc(sizeof(slnode)))==NULL)exit(1);q->data=x;q->next=p->next;p->next=q;return 1;}int slldelete(slnode*head,int i,datatype x){slnode*p,*q;int j;p=head;j=0;while(p->next!=NULL&&j<i-1)< p="">{p=p->next;j++;}if(j!=i-1){printf("the delete-position parameter is wrong!\n"); return 0;}q=p->next;p->next=p->next->next;x=q->data;free(q);}int sllget(slnode*head,int i,datatype*x){slnode*p;int j;p=head;j=0;while(p->next!=NULL&&j<i)< p="">{p=p->next;j++;}if(j!=i){printf("the get-position parameter is wrong!\n"); return 0; }*x=p->data;return 1;}int sllnotempty(slnode*head){if(head->next==NULL)return 0;else return 1;}linlistsort(slnode*head){slnode*curr,*pre,*p,*q;head->next=NULL;while(p!=NULL){curr=head->next;while(curr!=NULL&&curr->data<=p->data){pre=curr;curr=curr->next;}q=p;p=p->next;q->next=pre->next;pre->next=q;}}linlistinsert(slnode*head,datatype x){slnode*curr,*pre,*q;curr=head->next;pre=head;while(curr!=NULL&&curr->data<=x){pre=curr;curr=curr->next;}if((q=(slnode*)malloc(sizeof(slnode)))==NULL)exit(1); q->data=x;q->next=pre->next;}converse(slnode*head) {slnode*p,*q;p=head->next;head->next=NULL; while(p!=NULL){q=p;p=p->next;q->next=head->next; head->next=q;}}</i)<></i-1)<></i-1)<>。

单链表逆序1. 什么是单链表？单链表是一种常见的数据结构，它由一系列节点组成，每个节点包含一个数据元素和一个指向下一个节点的指针。

每个节点只能访问其后继节点，而无法直接访问前驱节点。

2. 单链表的逆序操作单链表的逆序操作是将链表中的节点按照相反的顺序重新排列。

例如，原始链表为1 -> 2 -> 3 -> 4 -> null，逆序后的链表为4 -> 3 -> 2 -> 1 -> null。

3. 实现方法方法一：迭代法迭代法是一种常见且简单的实现方式。

具体步骤如下：1.初始化三个指针：prev指向null，curr指向头节点，next指向curr的后继节点。

2.循环遍历整个链表：–将curr的next指针指向prev。

–将prev指针移到curr位置。

–将curr指针移到next位置。

–将next指针移到curr的后继位置。

3.遍历结束后，将头节点更新为prev。

代码示例：def reverseLinkedList(head):prev = Nonecurr = headwhile curr:next = curr.nextcurr.next = prevprev = currcurr = nexthead = prevreturn head方法二：递归法递归法是另一种常见的实现方式，它通过递归调用函数来实现链表的逆序。

具体步骤如下：1.终止条件：当链表为空或只有一个节点时，直接返回该节点。

2.递归调用：将链表的头节点的后继节点传入函数进行逆序操作。

3.将链表头节点的后继节点的next指针指向头节点，并将头节点的next指针置为null。

代码示例：def reverseLinkedList(head):if head is None or head.next is None:return headreversedHead = reverseLinkedList(head.next)head.next.next = headhead.next = Nonereturn reversedHead4. 示例假设原始链表为1 -> 2 -> 3 -> 4 -> null，我们使用上述两种方法对其进行逆序操作。

编写算法：实现带头结点单链表的逆置算法标题：探讨带头结点单链表的逆置算法实现及其应用在计算机科学和算法领域，链表是一种非常重要的数据结构，它能够以一种灵活的方式存储和组织数据。

在链表的操作中，逆置算法是一种常见且有用的操作，它能够将链表的顺序颠倒，为问题的解决提供便利。

本文将从简到繁，由浅入深地探讨带头结点单链表的逆置算法的实现及其应用。

1. 带头结点单链表的定义和特点带头结点单链表是一种特殊的链表结构，它在链表的头部增加了一个额外的结点，这个结点并不存储实际的数据，而是作为头结点来方便链表的操作。

带头结点单链表的特点是可以方便地插入和删除操作，同时也更容易处理空链表的情况。

2. 逆置算法的基本思路在带头结点单链表中，逆置算法的基本思路是从链表的第一个结点开始，依次改变每个结点的指针指向，将整个链表的方向颠倒过来。

在实现逆置算法时，需要注意处理好结点指针的指向关系，以免出现指针丢失或者内存泄露的情况。

3. 逆置算法的具体实现（1）需要判断链表是否为空或只有一个结点，如果是的话，则无需进行逆置操作。

（2）使用三个指针分别表示当前结点、前驱结点和后继结点，通过改变指针的指向来逆置链表。

（3）循环迭代链表，直到当前结点为空，完成链表的逆置操作。

4. 逆置算法的应用带头结点单链表的逆置算法在实际应用中有着广泛的使用场景，例如在字符串操作、图论算法、树算法等方面都能够发挥重要作用。

通过逆置算法，可以方便地实现字符串逆置、图的拓扑排序、二叉树镜像等复杂的数据操作。

带头结点单链表的逆置算法是一种非常重要的链表操作，它能够为问题的解决提供便利。

通过对逆置算法的深入理解和应用，可以为算法的设计和问题的解决提供更多的灵感和思路。

希望本文的内容能够帮助读者更深入地理解带头结点单链表的逆置算法，并在实际应用中发挥重要作用。

个人观点：带头结点单链表的逆置算法是一种非常有趣且实用的算法操作，它能够为链表操作和数据处理提供更多的灵活性和便利性。

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

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

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

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

具体实现方式如下：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->2->3->4，逆序后变为 4->3->2->1。

二、单链表逆序的实现方法实现单链表逆序的方法有很多，其中较为常见的是采用迭代法和递归法。

1.迭代法迭代法是通过一个循环来完成链表的逆序。

具体步骤如下：(1) 定义一个指针 pre，初始指向头节点，指向当前节点的前一个节点；(2) 定义一个指针 p，初始指向头节点；(3) 当 pre 不为空时，执行以下操作：a.将 p 指向的节点的 next 指针指向 pre；b.pre 指向 p；c.将 p 向后移动一个节点；(4) 循环结束后，p 指向的节点即为逆序后链表的头节点。

2.递归法递归法的思想是将链表不断拆分成子链表，然后对子链表进行逆序，最后将各子链表拼接起来。

具体实现如下：(1) 定义一个函数 reverse_list，接收一个链表节点作为参数；(2) 在函数中，判断传入的节点是否为空，如果为空，则返回空；(3) 将传入的节点的 next 指针指向的节点作为新的头节点，原节点的 next 指针指向 reverse_list(新头节点)；(4) 返回新头节点；(5) 在主函数中，调用 reverse_list(头节点)，返回的结果即为逆序后的链表。

三、单链表逆序的算法复杂度采用迭代法实现单链表逆序的时间复杂度为 O(n)，其中 n 为链表的长度。

采用递归法实现单链表逆序的时间复杂度也为 O(n)，但由于存在函数调用的开销，空间复杂度为 O(n)。

四、单链表逆序的应用实例单链表逆序在实际编程中应用广泛，例如在排序算法中，对链表进行逆序操作后，可以方便地进行快速排序等操作。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

具体步骤如下：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指针置为空，表示逆序链表的尾部。

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

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

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

单链表反转（4种算法实现）反转链表，又可以称为翻转或逆置链表，它们表达的是同一个意思。

以图 1 所示的链表为例经过反转（翻转、逆置）后，得到的新链表如图 2 所示：通过对比图 1 和图 2 中的链表不难得知，所谓反转链表，就是将链表整体“反过来”，将头变成尾、尾变成头。

那么，如何实现链表的反转呢？常用的实现方案有4 种，这里分别将它们称为迭代反转法、递归反转法、就地逆置法和头插法。

值得一提的是，递归反转法更适用于反转不带头节点的链表；其它3 种方法既能反转不带头节点的链表，也能反转带头节点的链表。

将以图1 所示，即不带头节点的链表为例，给大家详细讲解各算法的实现思想。

1、迭代反转链表该算法的实现思想非常直接，就是从当前链表的首元节点开始，一直遍历至链表的最后一个节点，这期间会逐个改变所遍历到的节点的指针域，另其指向前一个节点。

具体的实现方法也很简单，借助 3 个指针即可。

以图 1 中建立的链表为例，首先我们定义3 个指针并分别命名为beg、mid、end。

它们的初始指向如图 3 所示：在上图的基础上，遍历链表的过程就等价为：3 个指针每次各向后移动一个节点，直至mid 指向链表中最后一个节点（此时end 为NULL）。

需要注意的是，这 3 个指针每移动之前，都需要做一步操作，即改变 mid 所指节点的指针域，另其指向和 beg 相同。

1)在图 3 的基础上，我们先改变 mid 所指节点的指针域指向，另其和 beg 相同（即改为 NULL），然后再将 3 个指针整体各向后移动一个节点。

整个过程如图 4 所示：2)在图4 基础上，先改变mid 所指节点的指针域指向，另其和beg 相同（指向节点 1 ），再将 3 个指针整体各向后移动一个节点。

整个过程如图 5 所示：3)在图5 基础上，先改变mid 所指节点的指针域指向，另其和beg 相同（指向节点 2 ），再将 3 个指针整体各向后移动一个节点。

整个过程如图 6 所示：4)图 6 中，虽然 mid 指向了原链表最后一个节点，但显然整个反转的操作还差一步，即需要最后修改一次mid 所指节点的指针域指向，另其和beg相同（指向节点 3）。

链表的逆置
链表的逆置是一种常见的链表操作，它可以将链表中节点的顺序反转。

逆置链表的基本思路是将链表中的每个节点的指针指向前一个节点。

具体实现时，可以定义三个指针，分别指向当前节点、前一个节点和后一个节点，通过迭代的方式不断地将当前节点的指针指向前一个节点，直到遍历完整个链表。

逆置链表的时间复杂度为O(n)，其中n为链表的长度。

逆置链表在很多算法和数据结构中都有应用，例如链表的排序、链表的合并等。

需要注意的是，在逆置链表的过程中需要注意链表头节点的变化，以及空链表和只有一个节点的特殊情况的处理。

- 1 -。

单链表逆序三种⽅法准备定义结构体typedef struct Node{int data;struct Node* next;}Node,*pNode;链表初始化void initHead(pNode &head){head=new Node;head->next=NULL;}链表建⽴（尾插法）void bulidHead(pNode &head){pNode tail=head;tail->next=NULL;for(int i=0;i<10;i++){ //将0~9插⼊链表pNode p=new Node;p->data=i;tail->next=p;tail=p;tail->next=NULL;}}链表打印void printHead(pNode &head){pNode p=head->next;while(p){cout<<p->data<<"";p=p->next;}}链表销毁void destroyHead(pNode &head){pNode p=head;while(head){p=head->next;delete head;head=p;}}⼀、迭代法需要三个指针，前驱p1，当前p2，后继p3结束的条件是p2==null带头节点void reverse1(pNode &head){if(head->next!=NULL&&head->next->next!=NULL){ //⾄少有除头节点以外两个节点才能逆序pNode p1=head->next,p2=head->next->next,p3=NULL;while(p2){p3=p2->next;p2->next=p1;if(p1==head->next) { //放在出现环，可以这样写是因为环只可能p1->next=NULL; //出现在第⼀个和第⼆个节点之间。

实现单链表的就地逆置算法题目：有一个线性表（a1,a2,a3,....,an），采用带头节点的单链表L存储，设计一个算法将其就地逆置。

所谓“就地”指辅助空间应该为O（1）。

方法一：采用头插法先将L的头节点head的Next域置为NULL变成一个空链表，然后用p结点采用头插法插入到L中。

[java] view plaincopy1.static Node headInsert(Node head){2.if(head == null || head.next == null){3.System.out.println("逆置的单链表至少有2个结点");4.return null;5.}6.else{7.Node p = head.next;8.head.next = null;9.Node q = null;10.while(p != null){11.q = p;12.p = p.next;13.q.next = head;14.head = q;15.}16.return q;17.}18.}方法二：先将首节点的next置为NULL,用p,q指向单链表中相邻的两节点，将r指向q的下一个结点，然后同步后移。

当q=NULL时，表示指向原单链表的尾结点，将L的next域指向p即可。

[java] view plaincopy1.static Node invert(Node head){2.Node p,q,r;3.if(head == null || head.next == null){4.System.out.println("逆置的单链表至少有2个结点");5.return null;6.}7.else{8.p = head;9.q = p.next;10.while(q != null){11.r = q.next;12.q.next = p;13.p = q;14.q = r;15.}16.head.next = null;17.head = p;18.return head;19.}20.}[java] view plaincopy。

头插法将单链表原地逆转
如果你看到标题就知道我在说什么，那么出门左拐，⾃⼰动⼿写⼀下伪代码。

只有⾃⼰亲⼿写出和画出，才能更好的掌握。

现在有⼀个链表，Head指向头
然后使⽤temp保存Head中原来含有的结点的第⼀个结点，此时p指向第⼀个待插⼊结点
此时将head尾部置空
将 p 加⼊head头部，然后 p 后移⼀位。

往复多次，直到 p 空
1def reverse(self): #头插法原地逆转链表
2 p = self.head #p指向⼯作结点
3 self.head = None #将头指针看做⼀个空空的⼲净的头指针
4while p:
5 temp = self.head #保存头指针已经保存了的后续结点的第⼀个结点
6 self.head = p #将新结点头插法接到头指针上之后的步骤不能反过来哦，否则结果不是预期的结果
7 p = p.Next # STEP 1 :先将⼯作指针 p 后移到下⼀位
8 self.head.Next = temp # STEP 2 :然后再把原来的 head 的后⾯的结点 temp 连接到新加⼊的结点后⾯
9#注：STEP 1 和STEP 2 务必不要颠倒因为如果先执⾏ self.head.Next = temp 那么 p 的next就会变成 temp 是吧（你品品）。

数据结构-实现⼀个单链表的逆置1：这是⼀个经常被问到的⾯试题，也是⼀份⾮常基础的问题。

⽐如⼀个链表是这样的：1->2->3->4->5通过逆置后成为5->4->3->2->1。

最容易想到的⽅法是遍历⼀遍链表，利⽤⼀个辅助指针，存储遍历过程中当前指针指向的下⼀个元素，然后将当前节点元素的指针反转后，利⽤已经存储的指针往后⾯继续遍历。

代码如下：// ConsoleApplication15.cpp : 定义控制台应⽤程序的⼊⼝点。

//#include "stdafx.h"#include <malloc.h>#include <iostream>using namespace std;typedef struct node//定义链表结构体{int data;//节点内容node *next;//指向结构体的指针，下⼀个节点}node;node *create()//创建单链表{int i = 0;//链表中数据的个数node *head, *p, *q;//这些的本质是节点的地址int x = 0;head = NULL;q = NULL;//初始化q，q代表末节点p = NULL;while (1){printf("please input the data:");scanf_s("%d", &x);if (x == 0)break;//data为0时创建结束p = (node *)malloc(sizeof(node));//⽤于每次输⼊链表的数据p->data = x;if (++i == 1)//链表头的指针指向下⼀个节点{head = p;q = p;}else{q->next = p;//连接到链表尾端q = p;}q->next = NULL;/*尾结点的后继指针为NULL(空)*/}return head;}int length(node *head){int len = 0;node *p;p = head->next;while (p != NULL){len++;p = p->next;}return len;}void print(node *head){node *p;p = head;while (p)/*直到结点q为NULL结束循环*/{printf("%d ", p->data);/*输出结点中的值*/p = p->next;/*指向下⼀个结点*/}}node *search_node(node *head, int pos)//查找单链表pos位置的节点，返回节点的指针。

单链表的逆序（反转）单链表的逆序，本来不是算法这一部分的，怎奈何小伙伴们说，面试考的机率比较大，故此就把它跟算法放到一起了。

关于单链表逆序的基本知识点，请参加：/autumn20080101/article/details/7607148 当您看了上面博文的一部分，就能基本了解的时候，下面的内容应该适合您了。

下面的内容是对单链表逆序的关键知识点的一个总结。

博主客人觉得，单链表最关键的是本节点有一个指向下一个节点的指针（即后继节点指针），双向链表则是本节点有一个前驱节点和一个后继节点。

单链表时通过while循环，从头节点开始，直到节点的后继节点为空时，则到达了链表的尾部。

其实，单链表逆序，靠的就是下面的关键代码：1 while (head != NULL) {2 //在头节点改变之前，先获取下一个节点的指针3 next = head->Next;4 //头节点的下一个节点要改成它的上一个节点，是一个逆转的过程5 head->Next = prev;6 //上一个节点前移指向头节点7 prev = head;8 //头节点前移指向下一个节点9 head = next;10 }开发环境为：qt, c语言代码：完整代码：1 #include <QCoreApplication>23 //定义常数值4 #define LEN 35 const int MAX_NUM = 5;67 //定义节点8 //typedef struct tagNode* linkNode;9 typedef struct tagNode{10 int key;11 char value[LEN];12 struct tagNode* Next;13 } *Node, *linkList;1415 //生成链表16 linkList generateLinkList();17 //释放链表18 void freeLinkList(linkList list);19 //反转链表20 Node ReverseLinkList(Node head);21 //打印链表22 void printLinkList(linkList list);2324 int main(int argc, char *argv[])25 {26 QCoreApplication a(argc, argv);27 //生成链表28 Node head = generateLinkList();29 printf("反转之前的链表\r\n");30 //打印链表31 printLinkList(head);32 //链表反向33 head = ReverseLinkList(head);34 printf("反转之后的链表\r\n");35 //打印反向后的链表36 printLinkList(head);37 //释放链表内存38 freeLinkList(head);39 return a.exec();40 }41 /**42 * @函数名：generateLinkList43 * @参数：无44 * @返回值：链表对象指针(首节点)45 * @用途：生成链表对象46 * @作者：yangfy47 */48 linkList generateLinkList()49 {50 Node head, prev;51 //头节点52 head = (Node)malloc(sizeof(Node));53 head->key = 1;54 snprintf(head->value, LEN - 1, "%c", 65);55 //prev初始指向头节点56 prev = head;57 //初始化链表元素58 for(int i = 1; i < MAX_NUM; i++){59 Node pNode = (Node)malloc(sizeof(Node));60 //形成链表数据61 pNode->key = i + 1;62 pNode->Next = NULL;63 snprintf(pNode->value, LEN - 1, "%c", 65 + i);64 //前一个节点的下一个节点指向本节点(pNode)65 prev->Next = pNode;66 //把前一个节点置为本节点，进入下一个循环67 prev = pNode;68 }69 return head;70 }71 /**72 * @函数名：freeLinkList73 * @参数：head：头节点指针74 * @返回值：无75 * @用途：链表指针内存资源的释放。

单链表（头插法，尾插法创建，顺序输出链表，并返回链表长度）单链表（头插法，尾插法创建，顺序输出链表，并返回链表长度）代码如下:#include <stdio.h>#include <stdlib.h>#define LENG sizeof(struct node)//结点所占单元数struct node{ int data; struct node *next;};int main(){ struct node*create1();/*尾插法建⽴单链表*/ struct node*create2();//头插法建⽴单链表 int length(struct node*head);//返回单链表的长度，并输出各节点的值 struct node*head1,*head2; head1=create1(); head2=create2(); int leng1=length(head1); printf("\n"); printf("单链表1的长度为：%d",leng1); printf("\n"); int leng2=length(head2); printf("\n"); printf("单链表2的长度为：%d",leng2);return 0;}struct node *create1(){ struct node*head,*tail,*p; int e; head=(struct node *)malloc(LENG);//⽣成表头结点 tail=head; //尾指针只想表头 printf("please input a integer number:"); scanf("%d",&e); //输⼊第⼀个数 while(e!=0){ p=(struct node *)malloc(LENG);//⽣成新节点 p->data=e; tail->next=p; //新节点链接到表尾 tail=p; //尾指针指向新节点 printf("please input a integer number:"); scanf("%d",&e);}tail->next=NULL; //尾节点的next域置为空指针return head; //返回头指针}struct node *create2(){ struct node *head,*p; int e; head=(struct node*)malloc(LENG); head->next=NULL; printf("please input a integer number:"); scanf("%d",&e); while(e!=0){ p=(struct node *)malloc(LENG); p->data=e; p->next=head->next; head->next=p; printf("please input a integer number:"); scanf("%d",&e);}return head;};int length(struct node*head){int leng=0;struct node*p;p=head->next; //p指向⾸结点while(p!=NULL){printf("%d",p->data);printf(" ");leng++;p=p->next;}return leng;}运⾏结果：。

下面来看一下很经典的“单链表逆序”问题。

很多公司的面试题库中都有这道题，有的公司明确题目要求不能使用额外的节点存储空间，有的没有明确说明，但是如果面试者使用了额外的节点存储空间做中转，会得到一个比较低的分数。

如何在不使用额外存储节点的情况下使一个单链表的所有节点逆序？我们先用迭代循环的思想来分析这个问题，链表的初始状态如图（1）所示：图（1）初始状态初始状态，prev是NULL，head指向当前的头节点A，next指向A节点的下一个节点B。

首先从A节点开始逆序，将A节点的next指针指向prev，因为prev 的当前值是NULL，所以A节点就从链表中脱离出来了，然后移动head和next 指针，使它们分别指向B节点和B的下一个节点C（因为当前的next已经指向B节点了，因此修改A节点的next指针不会导致链表丢失）。

逆向节点A之后，链表的状态如图（2）所示：图（2）经过第一次迭代后的状态从图（1）的初始状态到图（2）状态共做了四个操作，这四个操作的伪代码如下：head->next = prev;prev = head;head = next;next = head->next;这四行伪代码就是循环算法的迭代体了，现在用这个迭代体对图（2）的状态再进行一轮迭代，就得到了图（3）的状态：图（3）经过第二次迭代后的状态那么循环终止条件呢？现在对图（3）的状态再迭代一次得到图（4）的状态：图（4）经过第三次迭代后的状态此时可以看出，在图（4）的基础上再进行一次迭代就可以完成链表的逆序，因此循环迭代的终止条件就是当前的head指针是NULL。

现在来总结一下，循环的初始条件是：prev = NULL;循环迭代体是：next = head->next;head->next = prev;prev = head;head = next;循环终止条件是：head == NULL根据以上分析结果，逆序单链表的循环算法如下所示：61 LINK_NODE *ReverseLink(LINK_NODE *head)62{63 LINK_NODE *next;64 LINK_NODE *prev = NULL;6566while(head != NULL)67{68 next = head->next;69 head->next = prev;70 prev = head;71 head = next;72}7374return prev;75}现在，我们用递归的思想来分析这个问题。