给你一个列表,删除列表的倒数第n个节点,并且返回链表的头节点你能尝试使用一趟扫描时限吗使用c++语言写程序。
时间: 2024-10-21 18:05:58 浏览: 17
1.3.2 给定一个链表,删除链表的倒数第N个节点,并且返回链表的头结点.md
在C++中,如果你有一个单向链表并且需要删除倒数第n个节点,而且要在一次遍历中完成操作,可以使用两个指针:一个快指针每次移动一步,另一个慢指针移动n步。当快指针到达链表尾部时,慢指针恰好停在倒数第n个节点前一个位置。然后你可以将慢指针指向的节点的下一个节点赋值给快指针指向的节点,使其跳过倒数第n个节点。
以下是相关的C++代码实现:
```cpp
#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* removeNthFromEnd(ListNode* head, int n) {
if (!head || !head->next || n == 0) return head;
ListNode* slow = head; // 慢指针
ListNode* fast = head; // 快指针
// 移动fast指针n+1次,使它到达倒数第n+1个节点
for (int i = 0; i < n + 1; ++i) {
if (fast) fast = fast->next;
}
// 如果fast为空,说明n大于链表长度,则直接返回原链表
if (!fast) return head;
// 让slow和fast同时移动直到相遇
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// 删除倒数第n个节点
if (slow != NULL) slow->next = slow->next->next;
return head;
}
// 测试函数
void printList(ListNode* head) {
while (head) {
std::cout << head->val << " -> ";
head = head->next;
}
std::cout << "NULL" << std::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);
printList(list); // 输出: 1 -> 2 -> 3 -> 4 -> 5 -> NULL
list = removeNthFromEnd(list, 2); // 删除倒数第二个节点
printList(list); // 输出: 1 -> 2 -> 4 -> 5 -> NULL
return 0;
}
```
这个程序会在一次遍历时找到并删除倒数第n个节点。
阅读全文