反转链表 - JZ35

题目描述

定义一个函数，输入一个链表的头结点，反转该链表并输出反转后链表的头结点。

思考题： 请同时实现迭代版本和递归版本。

数据范围： 链表长度 [0,30]

样例：

• 输入: 1->2->3->4->5->NULL
• 输出: 5->4->3->2->1->NULL

项目结构

.
├── go.mod              # Go 模块定义
├── types.go            # 链表类型定义和工具函数
├── solution.go         # 算法实现（你需要完成这个文件）
├── main.go             # 主函数和测试用例
├── solution_test.go    # 单元测试
└── README.md          # 说明文档

使用方法

1. 实现算法

在 solution.go 文件中实现两个函数：

• reverseList(head *ListNode) *ListNode - 迭代版本
• reverseListRecursive(head *ListNode) *ListNode - 递归版本

2. 运行测试

# 运行主程序，查看测试结果
go run .

# 运行单元测试
go test -v

# 运行基准测试
go test -bench=.

3. 检查代码格式

# 格式化代码
go fmt ./...

# 检查语法
go vet ./...

算法提示

迭代版本

使用三个指针：

• prev: 前一个节点
• curr: 当前节点
• next: 下一个节点

递归版本

递归思想：

1. 递归到链表尾部
2. 在回溯过程中反转指针
3. 返回新的头节点

时间和空间复杂度

• 迭代版本: 时间 O(n), 空间 O(1)
• 递归版本: 时间 O(n), 空间 O(n) (递归调用栈)

参考实现

在 solution.go 文件中提供了参考实现：

• reverseListIterativeSolution
• reverseListRecursiveSolution

建议先自己实现，然后再参考答案。