给一个链表,删除链表的倒数第n个结点,并返回链表的头结点,链表以-1为结尾,用c++
时间: 2025-05-08 22:15:57 浏览: 26
要在C++中删除链表的倒数第 n 个节点并返回修改后的链表头节点,可以采用双指针法解决这个问题。以下是详细的步骤及示例代码:
### 解决思路
1. **初始化两个指针**:`first` 和 `second` 都指向链表头部。
2. 先让第一个指针向前移动 n 步。
3. 然后同时移动两个指针直到第一个指针到达链表末尾。
4. 当第一个指针到达末尾时,第二个指针正好位于待删除节点前一个位置。
5. 删除第二个指针所指的下一个节点。
注意特殊情况如当需要移除的是头节点的时候处理方式有所不同。
```cpp
#include <iostream>
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* removeNthFromEnd(ListNode* head, int n){
if(!head || !n) return head;
// 创建虚拟头节点简化边界条件判断
ListNode dummy(0);
dummy.next = head;
ListNode* first = &dummy;
ListNode* second = &dummy;
for (int i = 0;i <= n && first != nullptr;i++) { // 第一步:先走 N+1步保证后续能定位到目标元素之前的一个节点
first = first->next;
}
while(first){ // 同时前进直至遍历完所有节点
first=first->next;
second=second->next;
}
// 移除操作
ListNode* toDelete = second -> next;
second -> next = second -> next -> next;
delete toDelete;
return dummy.next;
}
void printList(ListNode* node){
while(node){
std::cout << node->val << " ";
node=node->next;
}
std::cout<<"\n";
}
// 测试函数
int main(){
ListNode* l1=new ListNode(1);
l1->next=new ListNode(2);
l1->next->next=new ListNode(3);
l1->next->next->next=new ListNode(4);
l1->next->next->next->next=new ListNode(5);
printList(l1); // 打印原始列表
ListNode* result = removeNthFromEnd(l1, 2);
printList(result); // 打印结果列表
return 0;
}
```
上述程序实现了对单向链表的操作,它能够正确地从给定的链表中删除指定索引处(相对于尾巴计算的位置)的节点,并且保持其余部分不变序输出。
阅读全文