用C++语言编写一个程序,给定一个单向列表,请编写一个函数得到该列表中倒数第 个节点,给出必要注释。要求:空间复杂度为O(1),时间复杂度为O(n),且只能遍历一次列表。
时间: 2024-10-19 18:07:01 浏览: 26
在C++中,要实现这个功能,我们可以利用快慢指针的方法,即定义两个指针,一个普通指针每次移动一步,另一个初始时指向列表头,然后每次移动两步。当普通指针到达尾部时,快指针正好停在倒数第二个节点上。以下是示例代码:
```cpp
#include <iostream>
// 定义单链表节点结构体
struct ListNode {
int val; // 节点值
ListNode* next; // 指向下一个节点的指针
ListNode(int x) : val(x), next(NULL) {} // 构造函数
};
// 函数获取倒数第二个节点(仅遍历一次)
ListNode* getSecondLastNode(ListNode* head) {
if (head == nullptr || head->next == nullptr) { // 判断是否为空链表或只有一个节点
return nullptr;
}
ListNode* slow = head; // 普通指针,初始化为头节点
ListNode* fast = head->next; // 快速指针,初始化为第二节点
while (fast != nullptr && fast->next != nullptr) { // 当快指针还有下一个节点时继续循环
slow = slow->next; // 普通指针前进一步
fast = fast->next->next; // 快速指针前进两步
}
return slow; // 返回慢指针,即为倒数第二个节点
}
int main() {
// 示例链表:1 -> 2 -> 3 -> 4 -> 5
ListNode* list = new ListNode(1);
list->next = new ListNode(2);
list->next->next = new ListNode(3);
list->next->next->next = new ListNode(4);
list->next->next->next->next = new ListNode(5);
ListNode* secondLast = getSecondLastNode(list);
if (secondLast) {
std::cout << "倒数第二个节点的值是: " << secondLast->val << std::endl;
} else {
std::cout << "链表中没有倒数第二个节点." << std::endl;
}
delete list; // 释放内存
return 0;
}
```
在这个例子中,空间复杂度是O(1),因为我们只使用了固定数量的变量存储指针;时间复杂度是O(n),因为我们需要遍历整个链表一次。
阅读全文