编写一个程序exp5-2.py,用递归求解单链表中倒数第K个结点.
时间: 2024-05-07 22:23:44 浏览: 110
好的,下面是exp5-2.py的代码:
```python
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def findKthToTail(head, k):
if not head or k == 0:
return None
fast = head
slow = head
for i in range(k):
if not fast:
return None
fast = fast.next
while fast:
fast = fast.next
slow = slow.next
return slow
# 测试代码
if __name__ == '__main__':
# 创建单链表 1 -> 2 -> 3 -> 4 -> 5 -> 6
head = ListNode(1)
p = head
for i in range(2, 7):
node = ListNode(i)
p.next = node
p = p.next
# 测试用例
print(findKthToTail(head, 0)) # None
print(findKthToTail(head, 1).val) # 6
print(findKthToTail(head, 3).val) # 4
print(findKthToTail(head, 6).val) # 1
print(findKthToTail(head, 7)) # None
```
该程序使用了双指针法,其中一个指针先走k步,然后两个指针同时往后走,当先走的指针到达链表末尾时,后走的指针就指向了倒数第k个节点。如果遍历完整个链表,先走的指针仍然没有到达末尾,那么就说明k大于链表长度,返回None。
阅读全文