19 删除链表的第N个节点
解题思路
引入哑节点dummyNode:
- 防止出现空指针的情况,比如说链表总共有 5 个节点,题目就让你删除倒数第 5 个节点,也就是第一个节点,那按照算法逻辑,应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了,这就会出错。
- 循环结束条件为
fast == nullptr,这时指针fast指向nullptr,这是链表多出来的无效节点,导致正数和倒数的索引不对称。而引入哑节点之后,链表形成对称,正数和倒数对应的索引相同。 - 另外,引入
dummyNode之后,从dummyNode或nullptr出发,到达「正数第n个节点」或「倒数第n个节点」所需跳跃次数恰好为n
删除倒数第n个节点:
- 获取倒数第n + 1个节点实现删除
- 引入dummyNode之后,倒数第n + 1个就是正数第n + 1个,需要跳跃n + 1次
Solution
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode* dummyNode = new ListNode(-1);
dummyNode->next = head;
ListNode* fast = dummyNode, * slow = dummyNode;
// 获取正数第n + 1个节点
for(int i = 0; i < n + 1; i++){
fast = fast->next;
}
// 正数第n + 1个就是倒数第n + 1个
while(fast != nullptr){
fast = fast->next;
slow = slow->next;
}
// 删除第n个节点
ListNode* deleteNode = slow->next;
slow->next = deleteNode->next;
delete deleteNode;
return dummyNode->next;
}
};
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
private:
ListNode* findFromEnd(ListNode* head, int n){
// 创两个指针,初始都指向head
ListNode* p1 = head, * p2 = head;
// p2向右移动n步,使其与p1相距n,假设p1对应索引为index,那么p2对应索引为index + n
for(int i = 0; i < n; i++){
p2 = p2->next;
}
// 同时让两个指针运动,当p2移动到链表末尾的下一个位置(空指针)[index = size],p1刚好为倒数第n个节点[index = size - n]
while(p2 != nullptr){
p1 = p1->next;
p2 = p2->next;
}
// p1就是我们求的倒数第n个节点
return p1;
}
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
// dummyNode:因为可能删除头节点,所以我们需要一个虚拟头节点表示链表的开始
// 另外,头节点可能为空,返回dummyNode->next避免了判断头节点为空的情况
ListNode* dummyNode = new ListNode(-1);
dummyNode->next = head;
// 删除倒数第n个节点,需要遍历其前一个节点,也就是倒数第n + 1个节点
ListNode* target = findFromEnd(dummyNode, n + 1);
target->next = target->next->next;
return dummyNode->next;
}
};
复杂度分析
- 时间复杂度: O(n)
- 空间复杂度: O(1)