数据结构输入一个单向链表,输出该链表中倒数第k个结点,链表的最后一个结点是倒数第1个节点。
时间: 2023-11-20 07:50:19 浏览: 108
要输出单向链表中倒数第k个结点,可以使用双指针法。首先让一个指针p1指向链表的头结点,然后再让另一个指针p2指向第k个结点。接着同时移动这两个指针,直到p2指向链表的末尾为止,此时p1所指向的结点就是倒数第k个结点。
以下是示例代码:
```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
p1, p2 = head, head
for i in range(k-1):
if p2.next:
p2 = p2.next
else:
return None
while p2.next:
p1 = p1.next
p2 = p2.next
return p1
# 示例用法
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)
print(findKthToTail(head, 2).val) # 输出4
```
阅读全文