算法输入一个单向链表,输出该链表中倒数第k个结点,链表的最后一个结点是倒数第1个节点。
时间: 2023-11-20 20:50:01 浏览: 106
可以使用双指针法来解决该问题。首先让第一个指针从链表头开始向前移动k-1个节点,然后同时移动第一个和第二个指针,直到第一个指针到达链表尾部,此时第二个指针所指的节点即为倒数第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 not p1.next:
return None
p1 = p1.next
while p1.next:
p1 = p1.next
p2 = p2.next
return p2
# 测试代码
node1 = ListNode(1)
node2 = ListNode(2)
node3 = ListNode(3)
node4 = ListNode(4)
node5 = ListNode(5)
node1.next = node2
node2.next = node3
node3.next = node4
node4.next = node5
print(findKthToTail(node1, 2).val) # 输出4
```
阅读全文