📋 目录

1. 算法概述
2. 核心思想
3. 三指针法详解
4. 代码实现
5. 指针操作详解
6. 常见疑问解答
7. 算法复杂度分析
8. 扩展应用

---

🎯 算法概述

问题描述

给定一个单链表，要求将其反转，即改变所有节点的指向关系。

示例

原始链表：1 -> 2 -> 3 -> NULL
反转后：  3 -> 2 -> 1 -> NULL

算法特点

• 时间复杂度: O(n)
• 空间复杂度: O(1)
• 核心算法: 三指针法
• 适用场景: 单链表反转

---

💡 核心思想

基本思路

通过三个指针（prev、current、next）逐步反转每个节点的指向关系。

反转过程

1. 保存下一个节点：防止丢失后续节点信息
2. 反转当前节点：让当前节点指向前一个节点
3. 移动指针：准备处理下一个节点
4. 重复过程：直到处理完所有节点

关键理解

• 每次只处理一个节点
• 通过改变节点的next指针实现反转
• 需要临时保存下一个节点地址

---

🔄 三指针法详解

三个指针的作用

1. prev指针

struct Node* prev = NULL;  // 前一个节点指针

• 作用：指向已反转部分的最后一个节点
• 初始值：NULL（第一个节点反转后指向NULL）
• 更新：每次循环后指向当前处理的节点

2. current指针

struct Node* current = head;  // 当前处理节点指针

• 作用：指向正在处理的节点
• 初始值：head（链表头节点）
• 更新：每次循环后移动到下一个节点

3. next指针

struct Node* next = NULL;  // 下一个节点指针

• 作用：临时保存下一个节点的地址
• 初始值：NULL
• 更新：每次循环开始时保存current->next

指针关系图

初始状态：
prev=NULL  current=head  next=NULL
    ↓          ↓           ↓
   NULL    ->  1 -> 2 -> 3 -> NULL

第1次循环后：
prev=1     current=2     next=2
    ↓          ↓           ↓
NULL <- 1    2 -> 3 -> NULL

第2次循环后：
prev=2     current=3     next=3
    ↓          ↓           ↓
NULL <- 1 <- 2    3 -> NULL

第3次循环后：
prev=3     current=NULL   next=NULL
    ↓          ↓           ↓
NULL <- 1 <- 2 <- 3

---

💻 代码实现

完整代码

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

// 定义链表的节点
struct Node {
    int data;           // 数据
    struct Node* next;  // 指针，指向下一个节点
};

// 创建新节点
struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// 打印链表
void printList(struct Node* head) {
    struct Node* temp = head;
    while (temp != NULL) {
        printf("%d -> ", temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

// 🎯 链表反转算法 - 核心函数
struct Node* reverseList(struct Node* head) {
    // 三个指针：前一个、当前、下一个
    struct Node* prev = NULL;    // 前一个节点，初始为空
    struct Node* current = head; // 当前节点，从头开始
    struct Node* next = NULL;    // 下一个节点，初始为空
    
    printf("\n=== 开始反转链表 ===\n");
    printf("初始状态: prev=NULL, current=%d, next=NULL\n", current->data);
    
    // 只要当前节点不为空，就继续循环
    while (current != NULL) {
        printf("\n--- 处理节点 %d ---\n", current->data);
        
        // 第1步：保存下一个节点（因为改变current->next后会丢失）
        next = current->next;
        printf("第1步: next = current->next = %s\n", 
               next == NULL ? "NULL" : "下一个节点");
        
        // 第2步：反转指针（让当前节点指向前一个）
        current->next = prev;
        printf("第2步: current->next = prev = %s\n", 
               prev == NULL ? "NULL" : "前一个节点");
        
        // 第3步：移动prev指针
        prev = current;
        printf("第3步: prev = current = %d\n", current->data);
        
        // 第4步：移动current指针
        current = next;
        printf("第4步: current = next = %s\n", 
               current == NULL ? "NULL" : "下一个节点");
        
        // 打印当前状态
        printf("当前状态: ");
        if (prev != NULL) {
            printf("已反转部分: ");
            struct Node* temp = prev;
            while (temp != NULL) {
                printf("%d", temp->data);
                if (temp->next != NULL) printf(" <- ");
                temp = temp->next;
            }
        }
        printf(" | 剩余部分: ");
        if (current != NULL) {
            struct Node* temp = current;
            while (temp != NULL) {
                printf("%d", temp->data);
                if (temp->next != NULL) printf(" -> ");
                temp = temp->next;
            }
        } else {
            printf("NULL");
        }
        printf("\n");
    }
    
    printf("\n反转完成！返回prev指向的节点\n");
    return prev;  // prev现在指向新的头节点
}

// 释放链表内存
void freeList(struct Node* head) {
    struct Node* current = head;
    while (current != NULL) {
        struct Node* next = current->next;
        free(current);
        current = next;
    }
}

int main() {
    printf("=== 链表反转算法详细演示 ===\n\n");
    
    // 创建3个节点：5 -> 8 -> 12 -> NULL
    printf("1. 创建原始链表:\n");
    struct Node* head = createNode(5);
    head->next = createNode(8);
    head->next->next = createNode(12);
    
    printf("原始链表: ");
    printList(head);
    
    // 反转链表
    printf("\n2. 执行反转算法:\n");
    struct Node* reversedHead = reverseList(head);
    
    // 打印反转后的结果
    printf("\n3. 反转结果:\n");
    printf("反转后链表: ");
    printList(reversedHead);
    
    // 验证反转是否正确
    printf("\n4. 验证结果:\n");
    printf("原始: 5 -> 8 -> 12 -> NULL\n");
    printf("反转: 12 -> 8 -> 5 -> NULL\n");
    printf("结果: %s\n", 
           (reversedHead->data == 12 && 
            reversedHead->next->data == 8 && 
            reversedHead->next->next->data == 5) ? "✅ 正确" : "❌ 错误");
    
    // 释放内存
    freeList(reversedHead);
    
    return 0;
}

核心算法简化版

struct Node* reverseList(struct Node* head) {
    struct Node* prev = NULL;
    struct Node* current = head;
    struct Node* next = NULL;
    
    while (current != NULL) {
        next = current->next;      // 保存下一个节点
        current->next = prev;      // 反转指针
        prev = current;            // 移动prev指针
        current = next;            // 移动current指针
    }
    
    return prev;
}

---

🔍 指针操作详解

1. 两个不同的"next"

变量next vs 结构体成员next

struct Node* next = NULL;    // 这是一个变量，用来保存地址
current->next               // 这是结构体Node的成员，指向下一个节点

区别：

• 变量next：临时保存器，用来记住下一个节点的地址
• 结构体成员next：链表节点之间的连接器，指向下一个节点

更清晰的命名建议

struct Node* nextNode = NULL;  // 更清晰的变量名
struct Node* current = head;

while (current != NULL) {
    nextNode = current->next;  // 保存下一个节点
    current->next = prev;      // 反转指针
    prev = current;
    current = nextNode;
}

2. 四步操作详解

第1步：next = current->next;

next = current->next;

作用：保存下一个节点的地址
原因：因为下一步要修改current->next，如果不先保存就会丢失信息

第2步：current->next = prev;

current->next = prev;

作用：反转当前节点的指向
结果：当前节点指向前一个节点

第3步：prev = current;

prev = current;

作用：更新prev指针
结果：prev指向当前已处理的节点

第4步：current = next;

current = next;

作用：移动current指针到下一个节点
结果：准备处理下一个节点

3. 为什么需要四步？

反转指针 vs 移动指针

1. 反转指针（current->next = prev）：

   • 改变节点的连接关系
   • 实现链表反转

2. 移动指针（current = next）：

   • 让处理指针移动到下一个节点
   • 确保算法能够继续处理所有节点

如果不移动current会发生什么？

while (current != NULL) {
    next = current->next;
    current->next = prev;  // 反转指针
    prev = current;
    // current = next;     // 如果注释掉这行
    
    // 问题：current还是指向同一个节点
    // 下次循环会重复处理同一个节点
    // 导致无限循环！
}

---

❓ 常见疑问解答

Q1: 为什么需要保存next？

A: 因为修改current->next后会丢失下一个节点的信息，需要先保存。

Q2: 反转指针后为什么还要移动current？

A: 反转指针只是改变了连接关系，移动current是为了处理下一个节点，避免重复处理。

Q3: prev指针的作用是什么？

A: prev指向已反转部分的最后一个节点，新反转的节点需要指向它。

Q4: 为什么最后返回prev？

A: 循环结束后，prev指向原链表的最后一个节点，即新链表的头节点。

Q5: 空链表怎么处理？

A: 如果head为NULL，while循环不会执行，直接返回prev（NULL）。

Q6: 只有一个节点的链表怎么处理？

A: 第一次循环后，current变为NULL，循环结束，返回prev指向的节点。

---

📊 算法复杂度分析

时间复杂度

• O(n)：需要遍历链表中的每个节点一次
• n为链表的节点数量

空间复杂度

• O(1)：只使用了三个指针变量，空间使用量固定

性能特点

• 优点：空间效率高，原地反转
• 缺点：无法并行处理
• 适用性：适合大多数单链表反转场景

---

🚀 扩展应用

1. 反转链表的一部分

// 反转从第m个节点到第n个节点的部分
struct Node* reverseBetween(struct Node* head, int m, int n) {
    if (head == NULL || m >= n) return head;
    
    struct Node* dummy = createNode(0);
    dummy->next = head;
    struct Node* prev = dummy;
    
    // 移动到第m个节点的前一个节点
    for (int i = 1; i < m; i++) {
        prev = prev->next;
    }
    
    // 反转从第m个到第n个节点
    struct Node* current = prev->next;
    for (int i = m; i < n; i++) {
        struct Node* next = current->next;
        current->next = next->next;
        next->next = prev->next;
        prev->next = next;
    }
    
    return dummy->next;
}

2. K个一组反转链表

// 每K个节点为一组进行反转
struct Node* reverseKGroup(struct Node* head, int k) {
    if (head == NULL || k <= 1) return head;
    
    struct Node* current = head;
    int count = 0;
    
    // 检查是否有足够的节点
    while (current != NULL && count < k) {
        current = current->next;
        count++;
    }
    
    if (count < k) return head;  // 不足K个节点，不反转
    
    // 反转前K个节点
    struct Node* prev = NULL;
    current = head;
    for (int i = 0; i < k; i++) {
        struct Node* next = current->next;
        current->next = prev;
        prev = current;
        current = next;
    }
    
    // 递归处理剩余节点
    head->next = reverseKGroup(current, k);
    
    return prev;
}

3. 判断链表是否有环

// 使用快慢指针判断链表是否有环
bool hasCycle(struct Node* head) {
    if (head == NULL || head->next == NULL) return false;
    
    struct Node* slow = head;
    struct Node* fast = head->next;
    
    while (slow != fast) {
        if (fast == NULL || fast->next == NULL) return false;
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return true;
}

---

📝 总结

算法要点

1. 三指针法：prev、current、next三个指针协同工作
2. 四步操作：保存、反转、更新、移动
3. 原地反转：不需要额外空间
4. 一次遍历：时间复杂度O(n)

关键理解

• 每次只处理一个节点
• 通过改变next指针实现反转
• 需要临时保存下一个节点地址
• 反转和移动是两个不同的操作

应用场景

• 链表操作基础算法
• 面试常见题目
• 其他链表算法的基础

---

🔗 相关资源

学习资源

• LeetCode 206 - 反转链表
• 数据结构与算法教程
• 链表操作详解

扩展题目

• 反转链表的一部分
• K个一组反转链表
• 判断链表是否有环
• 找到链表的中间节点

---

本文档最后更新: 2024年
适用于: 数据结构与算法学习
维护者: 算法学习团队