6. 如何在 C 语言中实现链表的反转操作

# 1. 链表的基本概念

- ### 1.1 什么是链表？
链表是一种线性数据结构，由一系列节点组成，每个节点包含数据域和指针域。通过指针将这些节点串联起来，形成链式结构。

- ### 1.2 链表的结构特点
- 链表可以动态地分配内存空间，不像数组需要提前定义大小。
- 节点之间通过指针连接，可以在任意地方插入或删除节点。
- 链表的访问速度取决于查找的位置，而非索引，查找效率低于数组。

- ### 1.3 链表的分类
链表可分为单向链表、双向链表、循环链表等不同类型，每种类型的链表结构和特点略有区别。

- ### 1.4 链表与数组的区别
- 链表不需要连续的内存空间，可以随意分配和释放。
- 数组在内存中连续存储，访问速度快，但大小固定，插入删除元素慢。
- 链表适合频繁插入删除操作，数组适合查找操作。

- ### 1.5 链表的优缺点
- 优点：动态分配内存、插入删除快、无需提前定义大小。
- 缺点：访问速度较慢、占用更多内存空间、无法随机访问。

希望这些内容能帮助你更好地理解链表的基本概念和结构特点。

# 2. 链表的构建与操作

- ### 2.1 如何在 C 语言中实现链表的创建
- 创建链表的基本步骤：
1. 定义链表节点结构体，包含数据域和指针域；
2. 初始化头指针为空；
3. 动态分配内存，创建节点，填充数据域和指针域；
4. 调整指针连接节点，形成链表；
- 示例代码：

    #include <stdio.h>
    #include <stdlib.h>

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

    struct Node* createLinkedList(int data) {
        struct Node* head = (struct Node*)malloc(sizeof(struct Node));
        head->data = data;
        head->next = NULL;
        return head;
    }

    int main() {
        struct Node* head = createLinkedList(1);
        // 可以在此处继续添加节点操作
        return 0;
    }

- 代码总结：以上代码演示了如何在 C 语言中实现链表的创建，通过定义节点结构体和使用动态内存分配来构建链表。

- ### 2.2 链表的遍历方法
- 遍历链表的基本步骤：
1. 从头指针开始，依次访问每个节点的数据，并移动指针到下一个节点；
2. 使用循环语句实现遍历，直到遍历到链表末尾为止；
- 示例代码：

    void traverseLinkedList(struct Node* head) {
        struct Node* current = head;
        while (current != NULL) {
            printf("%d -> ", current->data);
            current = current->next;
        }
        printf("NULL\n");
    }

    int main() {
        struct Node* head = createLinkedList(1);
        head->next = createLinkedList(2);
        head->next->next = createLinkedList(3);
        traverseLinkedList(head);
        return 0;
    }

- 代码总结：上述代码展示了如何使用循环遍历链表，依次访问每个节点的数据，并输出链表的内容。

# 3. 链表的反转原理分析

- ### 3.1 为什么需要对链表进行反转操作
- 链表的结构决定了在实际应用中有一些操作需要对链表进行反转，例如逆序输出、翻转顺序等。
- 在某些算法题目中，需要对链表的顺序进行修改以满足特定要求。
- 反转链表可以提高链表的操作效率，减少对链表的遍历次数，提高算法的性能。

- ### 3.2 反转操作的常用方法
- 迭代方法：通过遍历链表，逐个修改节点的指针方向，实现链表的反转。
- 递归方法：递归地处理链表节点，并在递归的过程中完成链表的反转操作。

/** 
 * 函数功能：反转单链表
 * 输入参数：头节点指针 head
 * 返回值：反转后的头节点指针
 */
struct ListNode* reverseList(struct ListNode* head) {
    struct ListNode *prev = NULL;
    struct ListNode *curr = head;
    while (curr) {