python求链式表的倒数第k项
时间: 2024-09-21 12:02:35 浏览: 16
在Python中,如果你有一个链式表结构,例如`ListNode`,并且需要找到链表的倒数第k项,可以采用迭代或递归的方法。这里提供一种常见的双指针法:
首先,定义两个指针,`p1` 和 `p2`,初始化都为链表的头节点。然后让 `p2` 每次移动 k 步,同时 `p1` 只移动一步。当 `p2` 移动到链表尾部时,`p1` 所指向的就是链表的倒数第k项。
以下是具体的Python代码实现示例:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def find_kth_to_last(head, k):
if not head or not head.next or k <= 0:
return None
p1 = p2 = head
for _ in range(k - 1): # 先跳过k-1步
p2 = p2.next
while p2.next:
p1 = p1.next
p2 = p2.next
return p1.val # 返回倒数第k项的值
# 示例链表:1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
k = 2
result = find_kth_to_last(head, k) # 结果应该是4,因为倒数第二个元素是4
```