????????难度:简单
? ? ? ? 分类:链表
? ? ? ? 难度与分类由我所参与的培训课程提供,但需要注意的是,难度与分类仅供参考。以下内容均为个人笔记,旨在督促自己认真学习。
????????给你一个链表,删除链表的倒数第个结点,并且返回链表的头结点。
????????示例1:
????????输入:head=[1,2,3,4,5],n=2
????????输出:[1,2,3,5]
????????额外要求:
????????尝试使用一趟扫描实现?
???????? 额外要求提及需要一次扫描实现,但是需要注意的是单链表是从前向后遍历的。因此,删除倒数第n个节点就是删除正数第len-n个节点这个思路是从往后前遍历的。故不可行。
????????当需要删除链表的倒数第n个节点并返回头结点时,可以使用双指针的方法,通过一趟扫描实现。以下是解题思路:
使用双指针: 定义两个指针fast
和slow
,初始都指向虚拟头结点(dummy node)。
移动fast指针: 将fast
指针向前移动n+1步,使得fast
指针和slow
指针之间相差n个节点。这样,当fast
指针到达链表尾部时,slow
指针指向要删除节点的前一个节点。
移动fast和slow指针: 同时移动fast
和slow
指针,直到fast
指针指向链表尾部的下一个节点。
删除倒数第n个节点: 此时,slow
指针指向的节点就是要删除的节点的前一个节点。修改slow->next
指向slow->next->next
,即可删除倒数第n个节点。
返回头结点: 返回虚拟头结点的next
即为修改后的链表的头结点。
????????假设有一个链表 [1, 2, 3, 4, 5]
,并且要删除倒数第2个节点。
????????初始链表:? ??
1 -> 2 -> 3 -> 4 -> 5
????????初始化指针: 创建虚拟头结点,fast
和slow
指针都指向虚拟头结点。
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
^
slow fast
????????移动fast指针: 将fast
指针向前移动3步(n+1步),达到节点3。
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
^ ^
slow fast
????????移动fast和slow指针: 同时移动fast
和slow
指针,直到fast
指针到达链表尾部的下一个节点。此时,slow
指针指向要删除节点的前一个节点。
dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> null
^ ^
slow fast
????????删除倒数第n个节点: 删除节点3。
dummy -> 1 -> 2 -> 4 -> 5 -> null
^ ^
slow fast
????????返回头结点: 返回虚拟头结点的next
即为修改后的链表的头结点,即节点
1 -> 2 -> 4 -> 5
????????因此,删除倒数第2个节点后的链表为 [1, 2, 4, 5]
。
????????这种删除链表倒数第n个节点的算法的关键在于使用了两个指针(快指针和慢指针),通过它们之间的差距来找到要删除的节点。
????????快慢指针在这个问题中的原理是通过设置两个指针,一个快指针和一个慢指针,它们之间的步长差异为n+1。这种设置使得当快指针达到链表尾部时,慢指针正好指向要删除的节点的前一个节点。
双指针初始化: 初始时,快指针fast
和慢指针slow
都指向虚拟头结点。这样,它们之间的距离是0。
移动快指针: 快指针fast
先向前移动n+1步。这是因为我们希望fast
指针在慢指针slow
之前n个节点,为了处理删除倒数第n个节点的情况。
同时移动快慢指针: 接下来,我们同时移动快指针fast
和慢指针slow
,直到fast
指针到达链表尾部的下一个节点。由于fast
和slow
之间的初始距离是n+1,当fast
到达尾部时,slow
正好指向要删除节点的前一个节点。
删除倒数第n个节点: slow->next
就是要删除的节点,我们修改slow->next
指向slow->next->next
,即可删除倒数第n个节点。
返回头结点: 返回虚拟头结点的next
即为修改后的链表的头结点。
????????这种算法通过使用双指针,避免了对链表的多次遍历,实现了一趟扫描。由于fast
和slow
之间的距离是n+1,当fast
到达链表尾部时,slow
指向的就是要删除节点的前一个节点。这样就能在一次遍历中找到并删除倒数第n个节点。
#include <iostream>
using namespace std;
// 定义链表节点结构
struct ListNode {
int val; // 节点值
ListNode* next; // 下一个节点指针
ListNode(int x) : val(x), next(nullptr) {}
};
// 删除链表的倒数第n个节点
ListNode* removeNthFromEnd(ListNode* head, int n) {
// 创建一个虚拟头节点,方便处理删除头节点的情况
ListNode* dummy = new ListNode(0); // 创建虚拟头节点,值为0
dummy->next = head; // 将虚拟头节点指向传入的头节点
// 初始化快指针和慢指针,都指向虚拟头节点
ListNode* fast = dummy; // 快指针,用于提前移动n+1步
ListNode* slow = dummy; // 慢指针,用于定位要删除节点的前一个节点
// 快指针先向前移动n+1步
for (int i = 0; i <= n; ++i) {
fast = fast->next; // 快指针向前移动一步
}
// 同时移动快慢指针,直到快指针到达链表尾部的下一个节点
while (fast != nullptr) {
fast = fast->next; // 快指针向前移动一步
slow = slow->next; // 慢指针向前移动一步
}
// 删除倒数第n个节点
slow->next = slow->next->next;
return dummy->next; // 返回修改后的链表头
}
// 辅助函数:打印链表
void printList(ListNode* head) {
while (head != nullptr) {
cout << head->val << " "; // 输出节点值
head = head->next; // 移动到下一个节点
}
cout << endl;
}
int main() {
// 示例用法
ListNode* head = new ListNode(1); // 创建头节点,值为1
head->next = new ListNode(2); // 创建第二个节点,值为2
head->next->next = new ListNode(3); // 创建第三个节点,值为3
head->next->next->next = new ListNode(4); // 创建第四个节点,值为4
head->next->next->next->next = new ListNode(5); // 创建第五个节点,值为5
int n = 2;
ListNode* result = removeNthFromEnd(head, n); // 调用删除倒数第n个节点的函数
cout << "修改后的链表: ";
printList(result); // 打印修改后的链表
return 0;
}
????????时间复杂度:O(n)
????????空间复杂度:O(1)