输入一个单向链表,输出该链表中倒数第k个结点,链表的最后一个结点是倒数第1个节点。
时间: 2023-04-08 09:02:42 浏览: 116
链表中倒数第k个结点
可以回答这个问题。可以使用双指针法,定义两个指针p1和p2,p1先走k-1步,然后p1和p2一起走,当p1到达链表尾部时,p2指向的结点就是倒数第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
for i in range(k-1):
if not p1.next:
return None
p1 = p1.next
while p1.next:
p1 = p1.next
p2 = p2.next
return p2
```
其中head为链表头结点,k为倒数第k个结点。如果链表为空或k小于等于0,返回None。如果链表长度小于k,返回None。否则,p1先走k-1步,然后p1和p2一起走,直到p1到达链表尾部,此时p2指向的结点就是倒数第k个结点。
阅读全文