输出给定单链表的倒数第k个元素。
时间: 2024-10-12 22:06:22 浏览: 16
在计算机科学中,给定一个单链表和一个整数k,找到链表的倒数第k个节点是一个常见的算法问题。这个问题可以采用双指针法解决,即使用两个指针,一个快指针先走k步,另一个慢指针则正常移动。当快指针到达链表尾部时,慢指针正好指向倒数第k个元素。
以下是基本步骤:
1. 初始化两个指针,分别命名为`p1`(快速指针)和`p2`(慢速指针),并将它们都设置为链表的头节点。
2. `p1`向前移动k步。
3. 当`p1`到达链表尾部(`p1 == NULL`)时,`p2`的位置就是倒数第k个节点。
4. 否则,继续让`p1`和`p2`同时向后移动,直到`p1`到达链表尾部。
下面是Python伪代码示例:
```python
def find_kth_to_last(head, k):
p1 = head
p2 = head
# 快速指针先走k步
for _ in range(k):
if p1 is not None:
p1 = p1.next
# 当快指针到达链表尾部时,慢指针指向倒数第k个节点
while p1 is not None:
p1 = p1.next
p2 = p2.next
return p2
```
阅读全文