当前位置： 首页 > backend >正文

链表反转算法详解

backend 2025/7/26 15:39:00

📋 目录

  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 -> NULLprintf("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年
适用于: 数据结构与算法学习
维护者: 算法学习团队

http://www.xdnf.cn/news/16255.html

相关文章：

  • Fluent自动化仿真（TUI命令脚本教程）
  • springboot(3.4.8)整合mybatis
  • 【图像理解进阶】如何对图像中的小区域进行细粒度的语义分割？
  • WAIC2025预告｜英码深元AI一体机将亮相华为昇腾展区，以灵活部署的能力赋能行业智能化转型
  • Nginx简单介绍
  • Java-Properties类和properties文件详解
  • 图论：最小生成树
  • classgraph：Java轻量级类和包扫描器
  • linux C — udp，tcp通信
  • 【Chrome】下载chromedriver的地址
  • 深入解析浏览器存储方案：Cookie、localStorage和sessionStorage特性与应用
  • GPU 服务器ecc报错处理
  • Java排序算法之＜冒泡排序＞
  • 单片机（STM32-ADC模数转换器）
  • 优思学院｜QC七大手法之一的检查表应如何有效使用？
  • CSS 盒子模型学习版的理解
  • 数据结构 二叉树(1)
  • yarn在macOS上的安装与镜像源配置：全方位指南
  • 从 SQL Server 到 KingbaseES V9R4C12，一次“无痛”迁移与深度兼容体验实录
  • Orbbec开发---数据流与数据流操作
  • ZLMediaKit 源代码入门
  • Spring 策略模式实现
  • 【DeepRare】疾病识别召回率100%
  • SpringBoot学习路径二--Spring Boot自动配置原理深度解析
  • 教培机构如何开发自己的证件照拍照采集小程序
  • 萤石云替代产品摄像头方案萤石云不支持TCP本地连接-东方仙盟
  • 深入解析Hadoop MapReduce中Reduce阶段排序的必要性
  • 《Uniapp-Vue 3-TS 实战开发》自定义环形进度条组件
  • 人工智能冗余：大语言模型为何有时表现不佳（以及我们能做些什么）
  • 【js】ES2025新语法糖