输入一个单向链表,输出该链表中倒数第k个结点,链表的最后一个结点是倒数第一个结点,并输出测试用例
时间: 2024-09-21 09:04:13 浏览: 47
在单向链表中找到倒数第k个节点通常需要借助两个指针,一个快指针每次移动两步(如果链表长度大于k),另一个慢指针每次只移动一步。当快指针到达链表尾部时,慢指针就指向了倒数第二个节点。然后,只需让慢指针再向前移动k-1次,就能得到倒数第k个节点。
以下是算法的伪代码描述:
```python
def findKthToTail(head, k):
if not head or k <= 0:
return None
fast = head
slow = head
for _ in range(k - 1): # 跳过前k-1个节点
fast = fast.next
while fast and fast.next: # 当快指针到达链表尾部,慢指针就是倒数第二节点
fast = fast.next.next
slow = slow.next
if fast is None: # 如果k超出链表长度,则返回None
return None
else:
return slow # 返回倒数第k个节点
```
测试用例可以这样设计:
1. 链表只有一个元素,k=1,期望结果是这个唯一的元素。
2. 链表有三个元素A->B->C,k=2,期望结果是B节点。
3. 链表非常长,如A->B->...->Z(共26个元素),k=5,期望结果是倒数第五个元素,即Z节点。
4. 测试极端情况,k比链表长度还大,比如链表有n个元素,k=n+1,期望结果是None。
阅读全文