给定一个单向列表,请编写一个函数得到该列表中倒数第 个节点,给出必要注释。要求:空间复杂度为O(1),时间复杂度为O(n),且只能遍历一次列表。
时间: 2024-10-19 17:07:00 浏览: 25
MaxNumInts:编写一个函数,给出一个非负整数列表,将它们排列成尽可能大的数字
```python
# 定义一个函数`get_last_node`,接收一个单向链表作为输入参数`head`
def get_last_node(head):
"""
此函数用于获取给定单向链表的倒数第 n 个节点。通过遍历一次链表并使用两个指针法解决此问题,
其中快指针每次移动两步,慢指针每次移动一步,当快指针到达链表尾部时,慢指针恰好指向倒数第二个节点。
参数:
head (ListNode): 单向链表的头结点
返回:
ListNode: 如果链表非空,则返回倒数第二个节点;如果链表为空,则返回None
"""
# 初始化两个指针,fast和slow,都设为头节点
fast = slow = head
# 当fast指针未达到链表尾部(即fast != None)
while fast and fast.next:
# 快指针前进两步
fast = fast.next.next
# 慢指针前进一步
slow = slow.next
# 返回慢指针,即为倒数第二个节点
return slow
```
阅读全文