求链式线性表的倒数第K项python
时间: 2025-03-25 13:20:13 浏览: 36
### 单链表倒数第 K 个元素的 Python 实现
#### 方法一:两次遍历法
通过第一次遍历来计算链表的总长度 N,第二次遍历时定位到正序第 \(N-K+1\) 个节点即可。此方法简单易懂,但时间复杂度为 \(O(N)\)[^1]。
以下是具体实现代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_kth_from_end(head, k):
if not head or k <= 0:
return None
# 第一次遍历,统计链表长度
length = 0
current = head
while current:
length += 1
current = current.next
# 如果 k 超过链表长度,则返回 None
if k > length:
return None
# 计算目标位置
target_position = length - k
# 第二次遍历,找到目标节点
current = head
for _ in range(target_position):
current = current.next
return current
```
---
#### 方法二:双指针法
利用两个指针 `fast` 和 `slow`,初始都指向头结点。让 `fast` 先向前移动 \(k\) 步,之后再同时移动 `fast` 和 `slow`,直到 `fast` 到达链表末尾为止。此时,`slow` 所在的位置即为目标节点。这种方法只需遍历链表一次,时间复杂度为 \(O(N)\),空间复杂度为 \(O(1)\)[^2]。
以下是具体实现代码:
```python
def find_kth_from_end_two_pointers(head, k):
if not head or k <= 0:
return None
fast = slow = head
# 移动 fast 指针 k 步
for _ in range(k):
if not fast:
return None # 表明 k 大于链表长度
fast = fast.next
# 同时移动 fast 和 slow,直到 fast 达到链表末尾
while fast:
fast = fast.next
slow = slow.next
return slow
```
---
#### 方法三:基于递归的逆向访问
可以通过递归来反向访问链表,在回溯过程中记录已经访问过的节点数量,当计数值等于 \(k\) 时停止并返回对应的节点。然而,这种解法的空间复杂度较高,因为递归调用栈会占用额外内存,不推荐用于大规模数据处理[^3]。
以下是具体实现代码:
```python
def find_kth_from_end_recursive(head, k):
result = []
def helper(node):
if node is None:
return
helper(node.next)
result.append(node)
helper(head)
if k > len(result) or k <= 0:
return None
return result[k-1]
```
---
### 总结
上述三种方法各有优劣:
- **两次遍历法**适合初学者理解,逻辑清晰;
- **双指针法**最为高效,适用于实际开发场景;
- **递归法**虽然简洁,但在大链表上可能因堆栈溢出而失效。
最终建议优先采用双指针法实现该功能。
阅读全文
相关推荐












