用C++编写一个程序,给定一个单向列表,请编写一个函数,删除列表的倒数第k个节点。要求:空间复杂度为O(1),时间复杂度为O(n),且只能遍历一次列表。
时间: 2024-10-19 14:15:38 浏览: 23
在C++中,可以使用迭代的方式遍历链表,并同时维护两个指针,一个普通指针`prev`指向当前元素的前一个节点,另一个快指针`fast`每次移动两个节点。当`fast`到达链表尾部时,`prev`就会指向倒数第二个元素。然后我们可以简单地删除`prev`所指的节点,达到删除倒数第k个节点的效果。
下面是一个简单的示例代码:
```cpp
#include <iostream>
using namespace std;
// 定义链表节点结构体
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
void removeKthFromEnd(ListNode* head, int k) {
if (head == NULL || k <= 0) return; // 如果链表为空或k小于等于0,直接返回
ListNode* slow = head;
ListNode* fast = head;
// 快慢指针先找到链表尾部
for (int i = 0; fast && fast->next; ++i) {
fast = fast->next->next;
}
// 如果k大于链表长度,则不需要删除任何节点
if (fast == NULL) {
return;
}
// 慢指针回溯到倒数第k个节点的前一个位置
for (int i = 0; i < k - 1; ++i) {
slow = slow->next;
}
// 删除倒数第k个节点
if (slow != NULL) {
slow->next = slow->next->next;
}
}
// 测试函数
void printList(ListNode* head) {
while (head) {
cout << head->val << " ";
head = head->next;
}
cout << endl;
}
int main() {
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);
cout << "Original List: ";
printList(list);
removeKthFromEnd(list, 2); // 删除倒数第二个节点
cout << "After removing the second node from end: ";
printList(list);
return 0;
}
```
这个程序的空间复杂度为O(1),因为它只使用了固定的额外空间存储两个指针;时间复杂度为O(n),因为需要遍历链表两次,一次用于找到倒数第k个节点的位置,一次用于删除节点。
阅读全文