输入一个单链表,输出该链表中倒数第k个结点。
时间: 2023-08-31 17:12:57 浏览: 129
这个问题可以使用双指针来解决。我们可以定义两个指针p1和p2,首先将p1和p2都指向链表的头结点。然后让p1向前移动k个位置,此时p1和p2之间的距离为k。接着让p1和p2同时向前移动,直到p1指向链表的尾结点。此时p2所指向的结点就是链表中倒数第k个结点。
具体的算法实现如下:
1. 定义两个指针p1和p2,都指向链表的头结点。
2. 让p1向前移动k个位置。
3. 接着让p1和p2同时向前移动,直到p1指向链表的尾结点。
4. 此时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 p1.next:
p1 = p1.next
else:
return None
while p1.next:
p1 = p1.next
p2 = p2.next
return p2
```
其中,head为链表的头结点,k为倒数第k个结点。如果链表为空或者k小于等于0,直接返回None。否则,定义两个指针p1和p2,都指向头结点。首先让p1向前移动k-1个位置,然后让p1和p2同时向前移动,直到p1指向链表的尾结点。最后返回p2所指向的结点即可。
阅读全文