链表中倒数第k个节点 - JZ33

题目描述

输入一个链表，输出该链表中倒数第 k 个结点。

注意：

• k >= 1
• 如果 k 大于链表长度，则返回 NULL

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

样例：

• 输入：链表：1->2->3->4->5 ，k=2
• 输出：4 (节点值)

解题思路

这道题有多种解法：

1. 双指针法（推荐）： 使用快慢指针，快指针先走k步
2. 两次遍历法： 先计算链表长度，再定位目标节点
3. 栈辅助法： 利用栈的后进先出特性
4. 递归法： 利用递归的回溯特性

项目结构

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

使用方法

1. 实现算法

在 solution.go 文件中实现以下函数：

• findKthFromEnd(head *ListNode, k int) *ListNode - 主要实现

可选实现多种解法：

• findKthFromEndTwoPointers(head *ListNode, k int) *ListNode - 双指针法
• findKthFromEndTwoPass(head *ListNode, k int) *ListNode - 两次遍历法
• findKthFromEndStack(head *ListNode, k int) *ListNode - 栈辅助法
• findKthFromEndRecursion(head *ListNode, k int) *ListNode - 递归法

2. 运行测试

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

# 运行单元测试
go test -v

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

3. 检查代码格式

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

# 代码检查
go vet ./...

时间和空间复杂度分析

方法	时间复杂度	空间复杂度	说明
双指针法	O(n)	O(1)	最优解，一次遍历
两次遍历法	O(n)	O(1)	需要两次遍历
栈辅助法	O(n)	O(n)	需要额外栈空间
递归法	O(n)	O(n)	递归调用栈

关键点

1. 边界条件处理： 空链表、k=0、k大于链表长度
2. 双指针技巧： 快指针先走k步，然后快慢指针同时移动
3. 索引理解： 倒数第k个就是正数第(n-k+1)个
4. 空间优化： 双指针法是最优解

知识点

• 链表遍历
• 双指针技巧
• 边界条件处理
• 空间与时间的权衡