求链式线性表的倒数第K项分数 12 全屏浏览 切换布局 作者 DS课程组 单位 浙江大学 给定一系列正整数,请设计一个尽可能高效的算法,查找倒数第K个位置上的数字。 输入格式: 输入首先给出一个正整数K,随后是若干非负整数,最后以一个负整数表示结尾(该负数不算在序列内,不要处理)。 输出格式: 输出倒数第K个位置上的数据。如果这个位置不存在,输出错误信息NULL。 输入样例: 4 1 2 3 4 5 6 7 8 9 0 -1 输出样例: 7 代码长度限制 16 KB Python (python3) 时间限制 1200 ms 内存限制 128 MB Python (python2) 时间限制 1200 ms 内存限制 128 MB
时间: 2025-04-05 08:03:56 浏览: 56
为了求解“链式线性表的倒数第 K 项”这一问题,我们可以采用双指针法(快慢指针法)。这种方法可以在线性时间内完成操作,并且只使用常量额外空间。
以下是详细的思路:
---
### 思路分析
1. **初始化两个指针**
定义两个指针 `fast` 和 `slow`,都从头节点开始遍历链表或数组。
2. **让 fast 先走 k 步**
让 `fast` 指针先向前移动 k 步。这一步是为了保证后续两者的距离始终保持为 k。
3. **同时前进直到 fast 到达末尾**
接下来同步移动 `fast` 和 `slow` 指针,每次两者各前进一步。当 `fast` 到达链表末尾时,此时 `slow` 所指向的位置就是倒数第 K 个元素。
4. **特殊情况处理**
如果在整个过程中发现无法移动满 k 步,则说明链表长度不足 k,返回 NULL 表示无效结果。
---
### Python 实现代码
```python
def find_kth_from_end(k, nums):
# 初始化 slow 和 fast 指针
slow = fast = 0
count = 0 # 统计实际读取到的有效数字数量
for num in nums:
if num < 0: # 遇到结束标志 -1 停止循环
break
# 更新 fast 的位置
if count >= k: # 确保有足够步长再更新 slow
slow += 1
count += 1 # 移动 fast 并统计有效数字数量
# 如果有效数字少于 k,返回 NULL
if count < k:
return "NULL"
# 返回倒数第 K 个值
return nums[slow]
# 输入部分
k, *nums = map(int, input().split())
# 调用函数并打印结果
result = find_kth_from_end(k, nums)
print(result)
```
---
### 示例运行
#### 输入样例
```
4 1 2 3 4 5 6 7 8 9 0 -1
```
#### 输出结果
```
7
```
解释:按照上述步骤找到倒数第 4 个元素是 7。
---
### 时间复杂度和空间复杂度
- **时间复杂度**: O(n),其中 n 是列表中的有效数字个数。
- **空间复杂度**: O(1)。我们仅用了固定数量的变量 (`fast`, `slow`) 来存储状态,而不需要额外的数据结构。
---
阅读全文
相关推荐
















