LeetCode 19. 删除链表的倒数第N个节点
原题链接
中等
作者:
ShineShaye
,
2022-07-04 11:23:46
,
所有人可见
,
阅读 104
/**
* 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) {
// 删除节点 把该节点的前一个节点pre->next = pre->next->next即可
// 但头节点没有前一个节点,需要特判,为了避免特判,在前面先加一个冗余节点
auto dummy = new ListNode(-1);
dummy->next = head;
int len = 1;
for(auto p = head; p->next; p = p->next) len++;
int i = 0; // 指向冗余节点,删除时删除第一个结点
auto p = dummy;
while(i != len - n) // 倒数第n个结点是正数第len-n+1,前缀需要指向len-n
{
i += 1;
p = p->next;
}
p->next = p->next->next;
// 注意必须用p作副本循环,然后返回dummy->next。如果直接用dummy循环,返回head,那么碰到删除head时会错误
return dummy->next;
}
};