链表是基础且常用数据结构，反转链表极其适合新手用于理解指针、地址、结构体等概念。递归方式的链表反转代码简介，适合新手练习递归思路及写法。

链表结构及其方法的简单实现

链表的结构及其简单，但仍需注意细节，譬如分配新内存空间时需要if (n == NULL)以检测是否分配成功（这也是编写其他C语言程序时一重要良好习惯）。

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

Node* create_list(int value) {
    Node* n = malloc(sizeof(Node));
    if (n == NULL) perror("allocation error");

    n->next = NULL;
    n->value = value;
    return n;
}

Node* push_back(Node* root, int value) {
    Node* n = malloc(sizeof(Node));
    if (n == NULL) perror("allocation error");

    Node* p;
    for (p = root; p->next != NULL; p = p->next);
    n->next = NULL;
    n->value = value;
    p->next = n;
    return p;
}

void delete_list(Node* root) {
    Node* p = root;
    while (p != NULL) {
        Node* temp = p;
        p = p->next;
        free(temp);
    }
}

反转链表的两种方式

使用循环

• 反转链表最基础的写法。

通过根节点地址寻找到最后一个节点，从前往后依次反转。prev变量用以存储上一个节点的地址，cur变量用于存储当前节点地址。在每个循环中，创建一个临时变量temp以临时存储下一个节点的地址，将当前节点的next指针指向前一个节点以完成反转，再将prev和cur变量分别迭代当前节点和下一个节点。当cur迭代至NULL时循环终止，最后返回的prev即为新的根节点。

Node* reverse_list(Node* root) {
    Node* cur = root;
    Node* prev = NULL;
    while (cur != NULL) {
        Node* temp = cur->next;
        cur->next = prev;
        prev = cur;
        cur = temp;
    }
    return prev;
}

使用递归

• 十分简短但需要一定理解

递归程序通常比循环程序更加简短，但会带来一定程度上阅读者理解的困难。

对于递归程序，首先要写好停止条件，不然会陷入循环无法终止。反转链表的递归终止条件即为cur == NULL。每一次递归中，我们需要给函数传入当前节点的地址以及上一个节点的地址（否则无从获取），创建临时变量temp存储当前节点地址，将当前节点下一个节点的地址改为上一个节点的地址。随后对原来下一个节点调用递归函数。最后终止时返回的prev即为新的根节点地址。

Node* reverse_list_recursively(Node* cur, Node* prev) {
    if (cur == NULL) return prev;

    Node* temp = cur->next;
    cur->next = prev;
    return reverse_list_recursively(temp, cur);
}