链表是编程学习的一个难点。其实，在C语言编程以及单片机裸机开发中，链表运用并不多。但是如果想提升嵌入式技能水平或收入水平，可以考虑深入嵌入式系统层面（如参与操作系统设计、深入学习新的操作系统等），此时，链表技术至关重要。

本期讲解一道C语言的算法题——反转一个单向链表。

题目描述：

(资料图片仅供参考)

已知链表的节点类型如下：

typedef struct node{

int data;   struct node* next;

}Node;

现在有一条单链表，其节点类型为Node，链表的头节点为head，请设计一种方法反转该链表，并返回反转后的链表。

Part 1

链表的基本介绍

Q1: 什么是节点？

A1: 节点是链表的构成单元，节点类型本质上是结构体类型，如题中出现的Node类型。正常情况下，一个节点至少包含两个成员，一个成员保存该节点的数据，比如int data; 另一个成员是一个指针，比如Node *next，用于指向下一个节点。因此多个节点可以串在一起，构成链表。

Q2: 什么是链表？

A2: 百度百科中是这样定义链表的。“链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。”

核心：链表是一种存储结构。

可以将链表与数组进行对比，链表的优势在于：对存储单元进行插入/删除操作更灵活方便（节点是链表的构成单元，元素是数组的构成单元）、链表的容量可以动态改变（而数组一旦定义，则容量固定，可能会有溢出风险）。

Q3: 链表的分类有哪些？

A3: 根据节点之间的关系，可以分为单链表（一般指单向不循环链表）、双链表、循环单链表。

Part 2

解题思路

先确认下本题中的节点类型。

typedef struct node{           int data;           struct node* next;    }Node;

由于本题采用一个单向不循环链表，链表的尾节点的指针成员指向NULL，可在示意图中先补充地址NULL。

图示的原链表由4个节点构成，分别是节点A、B、C和D，他们的data（数据成员）的值依次是1、2、3和4。节点A是首节点，即head保存节点A的地址。节点A的next（指针成员）指向节点B，节点B的next指向节点C，节点C的next指向节点D，节点D的next指向NULL。

观察原链表和转换后的图示，可以看出转换后节点之间的指向关系将完全反过来，节点D最终成为首节点，head将保存它的地址。

思考，得出以下结论：

在单向链表中，若要遍历节点，必须从链表首节点开始逐个访问，所以反转链表时，必须要按照原链表节点顺序逐个操作。（即按照从节点A到节点D的顺序）除了尾节点外，更改每个节点的next（指针成员）值之前，必须先用指针指向在原链表中该节点的下一个节点（比如：在更改节点A的next为NULL之前，必须用指针指向节点B，否则将丢失数据）。head指针用于保存链表的首节点的地址，会随着节点的反转，逐渐移动（改变指向）。

Step1,定义两个特殊用途的指针。

//指针p用于指向待反转节点的前一个节点Node *P = NULL;//指针N用于指向待反转节点的后一个节点Node *N = head;//本示例中head指针指向的节点也就是待操作的节点

Step2,用指针N指向待操作节点的下一个节点，反转一个节点（改变待操作节点的next成员）。

N = N- >next;head- >next = P;

Step3,准备反转下个节点前，需要依次改变P指针和head指针。

P = head;head = N;

Step4,用指针N指向待操作节点的下一个节点，反转一个节点（改变待操作节点的next成员）。

此步骤和Step2相同，已开始重复的操作了。故之后的步骤将省略。

需要注意的是，当head指针在某次偏移之后，它将会指向原链表的尾节点（此时head->next == NULL为真），就说明此刻仅需要反转最后一个节点。

Part 3

示例代码

示例说明：

为了方便演示运行效果，将在主函数中构建4个Node类型的结构体变量，先对他们赋值，然后将他们串成链表，遍历链表，打印节点数据（预期打印：1，2，3，4）。之后反转链表，再次遍历链表，打印节点数据（预期打印：4，3，2，1）。

核心代码：链表反转函数

Node *list_reverse(Node *head){  Node *i;  Node *P = NULL;  Node *N = head;  if(head == NULL)    return NULL;  while(head- >next != NULL) //判断head是否为尾节点   {    N = N- >next;    head- >next = P;    P = head;    head = N;  }  head- >next = P; //反转最后一个节点   return head; }

主程序设计

int main(void){  Node A,B,C,D;  //分别对4个节点的data赋值，并将他们串成链表   A.data = 1; A.next = &B;  B.data = 2; B.next = &C;  C.data = 3; C.next = &D;   D.data = 4; D.next = NULL;  Node *head = &A;    printf("原链表：\\n");  list_output(head);  head = list_reverse(head);  printf("\\n反转后：\\n");  list_output(head);  return 0;}

运行结果

和预期一致，代码验证成功！